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?

Tidy

Note that a TreeMap does not require you to remove and reinsert a key to update its value. A put(key, value) call will update the value for a key if it (or an "equal" key value) is already in the map. – Corral

hmm, then that means i can't have values with the same key, whereas in a priority queue i think i can. – Tidy

You can use a custom comparator to solve this and wrap your key in an object (maybe solve ties by edge id for example.) – Implicit

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.

Harwin

"it is less work to track only the minimum element, using a heap" - More specifically a PriorityQueue allows you to peek at the head element in constant time. A TreeMap requires O(logn) to peek. They both require O(logn) anytime you actually pop that element off. – Gust

@Gust "A TreeMap requires O(logn) to peek.": Incorrect. TreeMap/TreeSet does that using .first() or .last() in O(1) https://mcmap.net/q/153506/-computational-complexity-of-treeset-methods-in-java – Woolf

@VyshnavRameshThrissur JMess was correct stating that heap is constant time for access to the head, while tree is log(n). What Pete was pointing out in his answer is that a constant number of comparisons (zero) are performed during the traversal to first or last; traversing to the head unconditionally takes the “left” node. But the traversal time still scales as log(n). Comparisons matter because they can take so much longer than tree traversal, but they don’t negate the time complexity difference for a peek at the head. – Harwin

Looking at the source code of TreeMap and TreeSet we see TreeSet.first() calls TreeMap.firstKey() which as @Harwin correctly points out does no comparisons, but does have to traverse to the leftmost leaf node. – Gust

Link to support @JMess: stackoverflow.com/a/11912711 – Jedidiah

Answer 2

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.

Eliott

Is there a standard data structure that provides log(N) time for removing as TreeSet does but also allows equal (from the equals method prospective) elements? – Complect

Answer 3

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.

Ellsworthellwood

good note, but you could mimic this behavior for O(m) space with a TreeMap too. Just manually remove biggest elements after a certain size is reached. – Jarvey

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.

Malca

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.

Petrick

interesting, the only answer that points out a real big O disadvantage for TreeMap. Do you have a source for the space complexity of a TreeMap? – Jarvey

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.

Anxious

Answer 7

I may be late to this answer but still.

They have their own use-cases, in which either one of them is a clear winner.

For Example:

1: https://leetcode.com/problems/my-calendar-i TreeMap is the one you are looking at

2: https://leetcode.com/problems/top-k-frequent-words you don't need the overhead of keys and values.

So my answer would be, look at the use-case, and see if that could be done without key and value, if yes, go for PQueue else move to TreeMap.

Mini

Answer 8

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

Implicit

Answer 9

I find TreeMap to be useful, when there is a need to do something like:

• find the minimal/least key, which is greater equal some value, using ceilingKey()
• find the maximum/greatest key, which is less equal some value, using floorKey()

If the above is not required, and it's mostly about having a quick option to retrieve the min/max - PriorityQueue might be preferred.

Yesteryear

Answer 10

Their difference on time complexity is stated clearly in Erickson's answer.

On space complexity, although a heap and a TreeMap both take O(n) space complexity, building them in actual programs takes up different amount of space and effort.

Say if you have an array of numbers, you can build a heap in place with O(n) time and constant extra space. If you build a TreeMap based on the given array, you need O(nlogn) time and O(n) extra space to accomplish that.

Jarlath

Answer 11

One more thing to take into consideration, PriorityQueue offers an api which return the max/min value without removing it, the time complexity is O(1) while for a TreeMap this will still cost you O(logn)

This could be clear advantage in case of readonly cases where you are only interested in the top end value.

Nanaam