Re: priority queue
Steve Wampler wrote:
Andreas Leitgeb wrote:
sara <sarajan82@gmail.com> wrote:
Thanks a lot but how can I implement priority queue using ArrayList?
Also, my main goal is to implement greedy set cover algorithm fast and
therefore I am trying to use a priority queue. Thanks.
The point is, that a PriorityQueue is only then efficient, if the
elements added do not change lateron. But this is not in your case:
with each element that you remove, you end up modifying possibly *all*
the other elements, so a PriorityQueue is just the wrong tool for this
task.
I'm wondering why the PriorityQueue has to be an ArrayList - there are
certainly 'better' data structures for implementing a PQ [a Heap comes
to mind...]. Just because Java doesn't supply a Heap in any of the
standard packages doesn't mean that it's not a better approach than
building a PQ from an ArrayList - which has so many of the disadvantages
Andreas and others have given. And there may well be better ways
than building a PQ using a Heap - I haven't looked at PQ implementations
in a long time.
So I'm not sure you should give up on the PQ, but consider more efficient
ways to implement it than relying directly using a data structure supplied
by Sun.
The java.util.PriorityQueue implementation looks like a heap
implementation to me, and the first comment inside its class body says
"Priority queue represented as a balanced binary heap: the two children
of queue[n] are queue[2*n+1] and queue[2*(n+1)].". Priority changes
could be made more efficient if the implementation provided a method to
do it directly.
However, I still don't see what the PriorityQueue brings to the party.
Normally, the merit of a PQ is finding a succession of head items
without having to scan the entire contents each time. In this case, the
OP intends scanning the entire set of nodes each time a head item is
removed, in order to subtract out the old head node's elements. The same
scan could determine the new largest subset.
As far as I can tell, any work done to keep the nodes in priority order
is unnecessary complication and wasted cycles.
Patricia