java 我什么时候应该在 PriorityQueue 上使用 TreeMap，反之亦然？

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

提问by iceburn

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?

似乎它们都允许您检索最小值，这是我对 Prim 算法所需要的，并强制我删除并重新插入一个键以更新其值。使用一个比另一个有什么优势，不仅仅是这个例子，而且一般来说？

回答by erickson

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 anykey, and not just the minimum, a heap will not suffice, and the extra overhead of the tree is justified.

一棵树更有条理，它需要更多的计算来维护该组织。但是如果你需要访问任何键，而不仅仅是最小值，堆是不够的，树的额外开销是合理的。

回答by Leo Yee

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 Melements 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 Mis just a constant like 10.

另外，由于优先级队列在维护数据全序方面的能力较弱，因此在一些特殊情况下具有优势。如果要跟踪 的M数组中最大的元素N，时间复杂度为O(N*LogM)，空间复杂度为O(M)。但是如果你在地图上做，时间复杂度是O(N*logN)，空间是O(N)。这是非常基本的，而在某些情况下我们必须使用优先级队列，例如M只是像 10 这样的常量。

回答by Generic Person

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).

我想指出两个差异（这可能与 Java 中的 PriorityQueue 和 TreeSet 之间的差异更相关？因为该问题被认为是该问题的重复）。

(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.

(1) PriorityQueue 可以有重复项，而 TreeSet 不能有重复项。因此，在 Treeset 中，如果您的比较器认为 2 个元素相等，则 TreeSet 将仅保留这 2 个元素中的一个并丢弃另一个。

(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.

(2) TreeSet 迭代器按排序顺序遍历集合，而 PriorityQueue 迭代器不按排序顺序遍历。对于 PriorityQueue 如果要按排序顺序获取项目，则必须通过重复调用 remove() 来销毁队列。

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

我假设讨论仅限于 Java 对这些数据结构的实现。

回答by BufBills

Rule of thumb about it is:

关于它的经验法则是：

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

TreeMap 有序地维护所有元素。（所以直观上，构建它需要时间）

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

PriorityQueue 只保证最小值或最大值。它的价格较低，但功能较弱。

回答by Dushyant Sapra

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.

1. PriorityQueue 允许重复（即具有相同的优先级）而 TreeMap 不允许。
2. PriorityQueue 的复杂度为 O(n)（当它增加其大小时），而 TreeMap 的复杂度为 O(logn)（因为它基于红黑树）
3. PriorityQueue 基于 Array 而在 TreeMap 中的节点彼此链接，因此包含 PriorityQueue 的方法将花费 O(n) 时间而 TreeMap 将花费 O(logn) 时间。

回答by abhilash_goyal

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-iTreeMap is the one you are looking at

1: https://leetcode.com/problems/my-calendar-iTreeMap 是你正在查看的

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

2：https: //leetcode.com/problems/top-k-frequent-words你不需要键和值的开销。

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.

所以我的答案是，查看用例，看看是否可以在没有键和值的情况下完成，如果是，则使用 PQueue 否则移动到 TreeMap。

回答by Andrew McKinlay

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.

区别之一是 remove(Object) 和 contains(Object) 在基于普通堆的 PriorityQueue（如 Oracle 的）中是线性的 O(N)，而对于 TreeSet/Map 则是 O(log(N))。

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.

因此，如果您有大量元素并执行大量 remove(Object) 或 contains(Object)，那么 TreeSet/Map 可能会更快。

回答by Juan Besa

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

这取决于您如何实现优先队列。根据 Cormen 的书第 2 版，最快的结果是使用斐波那契堆。