PriorityQueue 에 대하여

• java 에서  maxheap, minheap 구현이 필요할 때 쓸 수 있다. 
• 내부적으로 보면  Object[] queue  로 데이터를 관리하고 있음을 알 수 있다. default initial capacity 는 11 로 되어 있다.
• JavaDoc 에 의하면
• this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); 
• linear time for the remove(Object) and contains(Object) methods; 
• and constant time for the retrieval methods (peek, element, and size).
• 라고 한다.  Binary heap 에 넣으니  log(N) 이될것이고 ,  N  개를 넣으면 Nlog(N) 이 된다.
• 또한 PriorityQueue  는 synchronized 되지 않았고,  multithread  환경이라면  PriorityBlockingQueue 를 써야한다.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    private static final long serialVersionUID = -7720805057305804111L;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // non-private to simplify nested class access
    ...

}    

우선순위가 가장 높은것이 queue 배열의 맨 앞에 존재한다. poll 할때 보면 queue[0] 을 return 함을 볼 수 있다.

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

이런 이유로, Top K 의 어떤 데이터를 관리하려면, 
minHeap 에 넣고, K 개가 넘으면, poll()을 해서 뺀다.
그럼 Heap 에는 계속해서 큰 것들만 남아 있다. 
iterate 를 다 했다면, minHeap 에서 poll()을 차례대로 해서 reverse 하면, max K 개가 큰 순서대로 나온다.