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

Question

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 1

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.

Answer 2

Totally agree with Erickson on that priority queue only gives you the minimum/maximum element.

In addition, because the priority queue is less powerful in maintaining the total order of the data, it has the advantage in some special cases. If you want to track the biggest M elements in an array of N, the time complexity would be O(N*LogM) and the space complexity would be O(M). But if you do it in a map, the time complexity is O(N*logN) and the space is O(N). This is quite fundamental while we must use priority queue in some cases for example M is just a constant like 10.

Answer 3

There are 2 differences I would like to point out (and this may be more relevant to Difference between PriorityQueue and TreeSet in Java? as that question is deemed a dup of this question).

(1) PriorityQueue can have duplicates where as TreeSet can NOT have dups. So in Treeset, if your comparator deems 2 elements as equal, TreeSet will keep only one of those 2 elements and throw away the other one.

(2) TreeSet iterator traverses the collection in a sorted order, whereas PriorityQueue iterator does NOT traverse in sorted order. For PriorityQueue If you want to get the items in sorted order, you have to destroy the queue by calling remove() repeatedly.

I am assuming that the discussion is limited to Java's implementation of these data structures.

Answer 4

Rule of thumb about it is:

TreeMap maintains all elements orderly. (So intuitively, it takes time to construct it)

PriorityQueue only guarantees min or max. It's less expensive but less powerful.

Answer 5

It all depends what you want to achieve. Here are the main points to consider before you choose one over other.

1. PriorityQueue Allows Duplicate(i.e with same priority) while TreeMap doesn't.
2. Complexity of PriorityQueue is O(n)(when is increases its size), while that of TreeMap is O(logn)(as it is based on Red Black Tree)
3. PriorityQueue is based on Array while in TreeMap nodes are linked to each other, so contains method of PriorityQueue would take O(n) time while TreeMap would take O(logn) time.

Answer 6

One of the differences is that remove(Object) and contains(Object) are linear O(N) in a normal heap based PriorityQueue (like Oracle's), but O(log(N)) for a TreeSet/Map.

So if you have a large number of elements and do a lot of remove(Object) or contains(Object), then a TreeSet/Map may be faster.

Answer 7

It depends on how you implement you Priority Queue. According to Cormen's book 2nd ed the fastest result is with a Fibonacci Heap.