Priority Queue

* 우선 순위 큐

* Heap을 사용하는 알고리즘이다

* insert, delete시 heapify만 해주면 끝

알고리즘

package algo.priorityqueue;

public class MyPriorityQueue {

	private int top;
	private int initialCapacity;
	private int capacity;
	private Integer[] array;
	
	public MyPriorityQueue() {
		
		top = -1;
		initialCapacity = 1;
		capacity = initialCapacity;
		array = new Integer[initialCapacity];
		
	}

	public Integer offer(Integer item) {
		
		if(isFull())
			reAllocate();
		
		top++;
		array[top] = item;

		System.out.println("OFFER : " + item);
		
		buildHeap();
		
		return item;
	}
	
	public Integer poll() {
		
		if (isEmpty())
			return null;

		Integer item = array[0];
		System.out.println("POLL : " + item);
		
		swap(0, top);
		printArr(" Swap    -->  ");

		array[top] = null;
		top--;
		
		buildHeap();
		
		return item;
	}
	
	private void reAllocate() {
		
		Integer[] newArr = new Integer[capacity * 2];
		for (int i = 0; i < array.length; i++) {
			newArr[i] = array[i]; 
		}
		array = newArr;
		capacity = capacity * 2;
	}
	
	
	private boolean isFull() {
		return top == capacity - 1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	private void buildHeap() {
		
		int arrSize = top + 1;

		for (int i = arrSize / 2 - 1; i >= 0; i--)
			heapify(arrSize, i);
		
		printArr(" BUILDED HEAP -->  ");
		
	}
	
	/**
	 * arrSize를 받는 이유는
	 * extract 연산을 할때 swap후 마지막 요소는 이미 정렬된 상태라 없는 취급을 해야 하므로 
	 */
	private void heapify(int arrSize, int arrIdx) {

		int largest = arrIdx;
		int left = arrIdx * 2 + 1;
		int right = arrIdx * 2 + 2;

		// 왼쪽, 오른쪽 자식중 큰것을 선택
		if (left < arrSize && array[largest] < array[left])
			largest = left;

		if (right < arrSize && array[largest] < array[right])
			largest = right;

		// 자식들이 부모보다 크다면 swap
		// 그리고 다시 자식을 상대로 heapify
		if (largest != arrIdx) {
			swap(largest, arrIdx);
			
			printArr(" Heapify -->  ");
			
			heapify(arrSize, largest);
		}

	}

	private void swap(int i, int j) {

		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;

	}

	private void printArr(String msg) {

		System.out.print(msg);
		for (int i = 0; i < top + 1; i++)
			System.out.print(array[i] + " ");
		System.out.println();

	}

}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.heap.MyHeapSort;
import algo.merge.MyMergeSort;
import algo.priorityqueue.MyPriorityQueue;
import algo.quick.MyQuickSort;

public class Main {

	public static void main(String[] args) {

		MyPriorityQueue queue = new MyPriorityQueue();
		queue.offer(1);
		queue.offer(3);
		queue.offer(5);
		queue.offer(2);
		queue.offer(11);
		queue.offer(7);
		queue.offer(99);
		queue.offer(1);
		queue.offer(-1);
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();

	}
}

<결과>

OFFER : 1
 BUILDED HEAP -->  1 
OFFER : 3
 Heapify -->  3 1 
 BUILDED HEAP -->  3 1 
OFFER : 5
 Heapify -->  5 1 3 
 BUILDED HEAP -->  5 1 3 
OFFER : 2
 Heapify -->  5 2 3 1 
 BUILDED HEAP -->  5 2 3 1 
OFFER : 11
 Heapify -->  5 11 3 1 2 
 Heapify -->  11 5 3 1 2 
 BUILDED HEAP -->  11 5 3 1 2 
OFFER : 7
 Heapify -->  11 5 7 1 2 3 
 BUILDED HEAP -->  11 5 7 1 2 3 
OFFER : 99
 Heapify -->  11 5 99 1 2 3 7 
 Heapify -->  99 5 11 1 2 3 7 
 BUILDED HEAP -->  99 5 11 1 2 3 7 
OFFER : 1
 BUILDED HEAP -->  99 5 11 1 2 3 7 1 
OFFER : -1
 BUILDED HEAP -->  99 5 11 1 2 3 7 1 -1 
POLL : 99
 Swap    -->  -1 5 11 1 2 3 7 1 99 
 Heapify -->  11 5 -1 1 2 3 7 1 
 Heapify -->  11 5 7 1 2 3 -1 1 
 BUILDED HEAP -->  11 5 7 1 2 3 -1 1 
POLL : 11
 Swap    -->  1 5 7 1 2 3 -1 11 
 Heapify -->  7 5 1 1 2 3 -1 
 Heapify -->  7 5 3 1 2 1 -1 
 BUILDED HEAP -->  7 5 3 1 2 1 -1 
POLL : 7
 Swap    -->  -1 5 3 1 2 1 7 
 Heapify -->  5 -1 3 1 2 1 
 Heapify -->  5 2 3 1 -1 1 
 BUILDED HEAP -->  5 2 3 1 -1 1 
POLL : 5
 Swap    -->  1 2 3 1 -1 5 
 Heapify -->  3 2 1 1 -1 
 BUILDED HEAP -->  3 2 1 1 -1 
POLL : 3
 Swap    -->  -1 2 1 1 3 
 Heapify -->  2 -1 1 1 
 Heapify -->  2 1 1 -1 
 BUILDED HEAP -->  2 1 1 -1 
POLL : 2
 Swap    -->  -1 1 1 2 
 Heapify -->  1 -1 1 
 BUILDED HEAP -->  1 -1 1 
POLL : 1
 Swap    -->  1 -1 1 
 BUILDED HEAP -->  1 -1 
POLL : 1
 Swap    -->  -1 1 
 BUILDED HEAP -->  -1 
POLL : -1
 Swap    -->  -1 
 BUILDED HEAP -->