When should I use a TreeMap over a PriorityQueue and vice versa?

java priority-queue treemap
iceburn picture iceburn · Aug 19, 2010 · Viewed 18k times · Source

Seems they both let you retrieve the minimum, which is what I need for Prim's algorithm, and force me to remove and reinsert a key to update its value. Is there any advantage of using one over the other, not just for this example, but generally speaking?

Answer

erickson picture erickson · Aug 19, 2010

Generally speaking, it is less work to track only the minimum element, using a heap.

A tree is more organized, and it requires more computation to maintain that organization. But if you need to access any key, and not just the minimum, a heap will not suffice, and the extra overhead of the tree is justified.

Related questions

How do I use a PriorityQueue?

How do I get a PriorityQueue to sort on what I want it to sort on? Also, is there a difference between the offer and add methods?

Read More
Change priorityQueue to max priorityqueue

I have priority queue in Java of Integers: PriorityQueue<Integer> pq= new PriorityQueue<Integer>(); When I call pq.poll() I get the minimum element. Question: how to change the code to get the maximum element?

Read More
How does Java's PriorityQueue differ from a min-heap?

Why did they name PriorityQueue if you can't insertWithPriority? It seems very similar to a heap. Are there any differences? If no difference, then why was it named PriorityQueue and not Heap?

Read More