Search code examples
javadata-structurescollectionsheappriority-queue

How can I peek the tail of a java.util.PriorityQueue?

So I am playing with the source code of the java.util.PriorityQueue. You can check it here: http://kickjava.com/src/java/util/PriorityQueue.java.htm

I am in need to peek the tail of the queue. This class only offers peeking the head of the queue. Is there an easy way that I can modify this class to allow me to pick the tail?

I am looking for any change / smart hack in this class to allow me to do that. My first try was to peek queue[size] but it did not work.

Solution

  • Java's PriorityQueue, like most priority queues, is implemented with a heap.

    A heap is a data structure that maintains only the property that all parents are less than their children, or all parents are greater than their children. There is no inherent ordering among children.

    Thus, the only way to find the tail would be to do a linear search among the bottom layer, which costs O(n) time for a size n priority queue.