Java Collection - PriorityQueue 용법

특징

• Heap 자료구조를 구현함

주요 메소드

• http://developer.android.com/reference/java/util/PriorityQueue.html  
• PriorityQueue(), PriorityQueue(int initialCapacity, Comparator<? super E> comparator) - 생성자
• Boolean add(E o) - 요소를 집어넣는 메소드, 내부적으로 offer(E o)를 호출하는데 offer(E o)와 동일하다고 보면 된다.
• E poll() - 큐에서 top priority 요소를 꺼내는 메소드
• E peek() - 큐에서 top priority 요소를 꺼내지는 않고 보는 메소드
• 그 밖에 size(), remove(Object o), clear() 등도 있다.

PriorityQueue를 이용하여 min heap과 max heap을 만드는 방법

• 기본 생성자 - PriorityQueue() - 를 사용하면 min heap이 되고 역순으로 비교하는 comparator를 사용하면 max heap이 된다. 
• 특별히 Collections.reverseOrder()가 제공된다. 대신 custom comparator를 사용할 수 있는 생성자에선 initial capacity도 함께 지정할 수 밖에 없다. 

Example

• min heap과 max heap을 유지하면서 median값을 O(log n)에 제공하는 메소드

private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, Collections.reverseOrder());

// 하위 수는 maxHeap에, 상위 수는 minHeap에 넣는다
// maxHeap의 개수가 minHeap과 같거나 하나 많도록 유지한다
public void addNumber(int number) {
    if (maxHeap.size() == minHeap.size()) {
        if ((minHeap.peek() != null) && number > minHeap.peek()) {
            maxHeap.offer(minHeap.poll()); // move the smallest of minHeap to maxHeap
            minHeap.offer(number);
        } else {
            maxHeap.offer(number);
        }
    } else {
        if (number < maxHeap.peek()) {
            minHeap.offer(maxHeap.poll());
            maxHeap.offer(number);
        } else {
            minHeap.offer(number);
        }
    }
}

public double getMedian() {
    if (maxHeap.isEmpty()) return 0d; // error

    if (maxHeap.size() == minHeap.size()) {
        return (minHeap.peek() + maxHeap.peek()) / 2;
    } else if (maxHeap.size() > minHeap.size()) {
        return maxHeap.peek();
    }
}