我什么时候应该使用 TreeMap 而不是 PriorityQueue，反之亦然？
似乎它们都让你检索最小值，这就是 Prim 算法所需的，并迫使我删除并重新插入密钥以更新其值。不仅对于这个例子，而且一般来说，使用其中一种比另一种有什么优势吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（11）
一般来说，使用堆仅跟踪最小元素的工作量较少。
树的组织性更强，并且需要更多的计算来维护该组织。但是，如果您需要访问任何键，而不仅仅是最小的键，则堆是不够的，并且树的额外开销是合理的。
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.
我想指出两个差异（这可能与 Java 中 PriorityQueue 和 TreeSet 之间的区别？ 因为该问题被视为该问题的重复）。
(1) PriorityQueue 可以有重复项，而 TreeSet 不能有重复项。因此，在 Treeset 中，如果比较器认为 2 个元素相等，TreeSet 将仅保留这 2 个元素之一，并丢弃另一个。
(2) TreeSet 迭代器按排序顺序遍历集合，而 PriorityQueue 迭代器不按排序顺序遍历。对于 PriorityQueue 如果你想按排序顺序获取项目，你必须通过重复调用remove()来销毁队列。
我假设讨论仅限于这些数据结构的 Java 实现。
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.
完全同意埃里克森的观点，优先级队列只给你最小/最大元素。
另外，由于优先级队列在维护数据总序方面能力较弱，因此在一些特殊情况下具有优势。如果您想跟踪
N数组中最大的M元素，时间复杂度将为O(N*LogM)，空间复杂度为O(N*LogM)复杂度为O(M)。但如果您在地图中执行此操作，则时间复杂度为O(N*logN)，空间复杂度为O(N)。这是非常基本的，但在某些情况下我们必须使用优先级队列，例如M只是一个像 10 这样的常量。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 ofN, the time complexity would beO(N*LogM)and the space complexity would beO(M). But if you do it in a map, the time complexity isO(N*logN)and the space isO(N). This is quite fundamental while we must use priority queue in some cases for exampleMis just a constant like 10.经验法则是：
TreeMap 有序地维护所有元素。 （所以直观上来说，构造它是需要时间的）
PriorityQueue只保证min或max。它更便宜，但功能更弱。
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.
这完全取决于您想要实现的目标。在您选择其中之一之前，请考虑以下要点。
It all depends what you want to achieve. Here are the main points to consider before you choose one over other.
区别之一是，在基于普通堆的 PriorityQueue（如 Oracle 的）中，remove(Object) 和 contains(Object) 是线性 O(N)，但对于 TreeSet/Map 是 O(log(N))。
因此，如果您有大量元素并执行大量删除（对象）或包含（对象），那么 TreeSet/Map 可能会更快。
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.
我可能迟到了这个答案，但仍然如此。
他们有自己的用例，其中任何一个都是明显的赢家。
例如：
1：https://leetcode.com/problems/my-calendar-i TreeMap 是您正在查看的
2： https://leetcode.com/ issues/top-k-frequent-words 你不需要键和值的开销。
所以我的答案是，查看用例，看看是否可以在没有键和值的情况下完成，如果是，则使用 PQueue，否则移至 TreeMap。
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.
这取决于您如何实现优先级队列。根据 Cormen 的书第二版，最快的结果是斐波那契堆。
It depends on how you implement you Priority Queue. According to Cormen's book 2nd ed the fastest result is with a Fibonacci Heap.
我发现 TreeMap 很有用，当需要执行以下操作时：
如果上述不是必需的，并且主要是有一个快速选项来检索最小值/最大值 - PriorityQueue 可能是首选。
I find TreeMap to be useful, when there is a need to do something like:
If the above is not required, and it's mostly about having a quick option to retrieve the min/max - PriorityQueue might be preferred.
他们在时间复杂度上的差异在埃里克森的回答中清楚地说明了。
在空间复杂度上，虽然堆和 TreeMap 的空间复杂度都是 O(n)，但在实际程序中构建它们所占用的空间和精力是不同的。
假设您有一个数字数组，您可以使用 O(n) 时间和恒定的额外空间就地构建一个堆。如果基于给定数组构建 TreeMap，则需要 O(nlogn) 时间和 O(n) 额外空间来完成此任务。
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.
还要考虑的一件事是，PriorityQueue 提供了一个 api，它返回最大/最小值而不删除它，时间复杂度为 O(1)，而对于 TreeMap，这仍然会花费您 O(logn)
这可能是明显的优势只读情况，您只对顶端值感兴趣。
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.