Clever Geek Handbook

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

So, I am playing with the source code java.util.PriorityQueue

. You can check it out here: http://kickjava.com/src/java/util/PriorityQueue.java.htm

I need to look at the back of the line. This class only offers a look at the head of the queue. Is there an easy way that I can modify this class to allow me to select the tail?

I'm looking for any changes / smart hacks in this class to allow me to do this. My first attempt was to peek queue[size]

, but it didn't work.

+3


source to share


2 answers


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

A heap is a data structure that only supports the property that all parents are smaller than their children, or all parents are larger than their children. Children have no intrinsic order.



So the only way to find the tail is to do a linear search among the lowest level that stands O(n)

for the size priority queue n

.

+4


source


Yes, but at the expense of the complexity of the extra space.

PriorityQueue pq_new = new PriorityQueue <> (Collections.reverseOrder ());

or if you haven't imported Collections, then:



PriorityQueue pq_new = new PriorityQueue <> (java.util.Collections.reverseOrder ());

Now add the elements of your PriorityQueue to this pq_new. So pq_new.peek () will give you the answer you want, i.e. the tail element of your original PriorityQueue.

+1


source






More articles:


All Articles