Get the tail of a PriorityQueue?

[jimi_usenet]

Hi all,

I have a class MaxCapacityPriorityQueue that extends
java.util.PriorityQueue, and has the added functionallity that it has a
maximum capacity, and it doesn't grow above this limit (when the queue
is full and an additional object is added, it removes the last object
in the queue, ie the "smallest" one according to the comparator). All
this works fine.
But now I would like to check the "biggest" (according to the
comparator) object in the queue, ie the one in the tail. But there is
no such function. I only see peek() and poll() wich gives me the
*head*.
Is there a better priority queue out there, that has this
functionallity? Or is there a way for me to add it in my subclass of
PriorityQueue? The internal Object[] queue in this class is private, so
I can't access it directly.

 

[Stefan Schulz]

Since a PriorityQueue offers fast access to the lowest element, you
will want to use a reverseOrder comparator for this task (See
java.util.Collections). However, part of the beauty of Priority Queues
is that they can be very efficiently implemented using a heap
(described in most textbooks), which offers no real guarantees other
then being easily able to find and maintain the minimum element.

Since the very good performance in the case of the findMin operation
comes at the price of a less then totally structured ordering, you can
either use another queue implementation which uses a sorted list as
backing structure, or try to muck around with re-implementing a heap
which seeks out a maximum (in your case: Minimum) element when it has
no more space. Note that this is potentially as expensive as keeping a
sorted list, since an "overflow insert" will take as long as the number
of elements in the PQ, instead of only log(n).

 

[Chris Uppal]

I have a class MaxCapacityPriorityQueue that extends
java.util.PriorityQueue, and has the added functionallity that it has a
maximum capacity, and it doesn't grow above this limit (when the queue
is full and an additional object is added, it removes the last object
in the queue, ie the "smallest" one according to the comparator). All
this works fine.
But now I would like to check the "biggest" (according to the
comparator) object in the queue, ie the one in the tail. But there is
no such function

I think you may be misunderstanding the priority heap data-structure (of which
java.util.PQ is an implementation). The point is that it gains efficiency by
/not/ keeping a completely sorted list of all the elements. So, although it
can efficiently find the first (least) element in the queue it does not know
which element is the last (greatest).

You might be able to get the effect you want by using two PQs, with opposite
comparators. I'm not sure whether that would have any efficiency benefits over
just keeping a completely sorted list of elements internally.

-- chris

 

[Stefan Schulz]

Not really, since any element removed from one by poll() would need to
be removed from the other, leading to an iteration over the entire
second heap.

 

[Chris Uppal]

Not really,

Not really what ?

[...] any element removed from one by poll() would need to
be removed from the other, leading to an iteration over the entire
second heap.

Good point.

Inserting into a sorted array would be O(N) too (in element moves, not
comparisons).

Obvious solution[*]: use a java.io.TreeSet.

-- chris

[*] In retrospect.