53

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?

iceburn
  • 987
  • 3
  • 13
  • 16
  • 3
    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. – Stephen C Aug 19 '10 at 18:28
  • hmm, then that means i can't have values with the same key, whereas in a priority queue i think i can. – iceburn Aug 19 '10 at 18:38
  • You can use a custom comparator to solve this and wrap your key in an object (maybe solve ties by edge id for example.) – Juan Besa Aug 19 '10 at 20:45

11 Answers11

55

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.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • 17
    "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. – JMess Apr 28 '17 at 17:00
  • @JMess "A TreeMap requires O(logn) to peek.": Incorrect. TreeMap/TreeSet does that using .first() or .last() in O(1) https://stackoverflow.com/a/14379571/5649620 – Vyshnav Ramesh Thrissur May 04 '21 at 17:36
  • 1
    @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. – erickson May 05 '21 at 18:35
  • Looking at the source code of TreeMap and TreeSet we see TreeSet.first() calls TreeMap.firstKey() which as @erickson correctly points out does no comparisons, but does have to traverse to the leftmost leaf node. – JMess May 05 '21 at 20:03
  • 1
    Link to support @JMess: https://stackoverflow.com/a/11912711 – h8pathak Jul 12 '22 at 01:22
15

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.

Community
  • 1
  • 1
Generic Person
  • 351
  • 1
  • 5
  • 10
  • 1
    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? – beemaster Jan 08 '17 at 15:46
14

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.

user3207158
  • 619
  • 2
  • 5
  • 22
Leo Yee
  • 141
  • 1
  • 2
  • 4
    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. – A1m Nov 05 '17 at 06:44
9

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.

elif
  • 5,427
  • 3
  • 28
  • 28
BufBills
  • 8,005
  • 12
  • 48
  • 90
7

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.
Dushyant Sapra
  • 585
  • 1
  • 8
  • 16
  • 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? – A1m Nov 05 '17 at 06:51
5

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.

Andrew McKinlay
  • 2,431
  • 1
  • 24
  • 27
3

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.

abhilash_goyal
  • 711
  • 1
  • 10
  • 31
0

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

Juan Besa
  • 4,401
  • 5
  • 24
  • 25
0

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.

Gil Shapir
  • 119
  • 1
  • 7
0

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.

cmhzc
  • 60
  • 1
  • 8
0

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.

Amer Qarabsa
  • 6,412
  • 3
  • 20
  • 43