45

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

4

10 回答 10

48

一般来说，使用堆只跟踪最小元素的工作量较少。

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

于 2010-08-19T18:15:37.197 回答
15

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

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

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

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

于 2016-07-14T20:19:12.923 回答
12

完全同意 Erickson 在该优先级队列上的观点只为您提供最小/最大元素。

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

于 2015-08-23T23:53:13.493 回答
9

关于它的经验法则是：

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

PriorityQueue 只保证最小值或最大值。它更便宜，但功能更弱。

于 2015-10-13T18:36:22.957 回答
7

这一切都取决于您想要实现的目标。以下是在您选择其中一个之前要考虑的要点。

  1. PriorityQueue 允许重复（即具有相同优先级），而 TreeMap 不允许。
  2. PriorityQueue 的复杂度是 O(n)（当它增加它的大小时），而 TreeMap 的复杂度是 O(logn)（因为它是基于红黑树）
  3. PriorityQueue 是基于数组的，而 TreeMap 中的节点是相互链接的，因此包含 PriorityQueue 的方法需要 O(n) 时间，而 TreeMap 需要 O(logn) 时间。
于 2017-06-17T17:19:27.560 回答
4

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

因此，如果您有大量元素并执行大量删除（对象）或包含（对象），那么 TreeSet/Map 可能会更快。

于 2015-04-23T14:24:42.517 回答
2

我可能迟到了这个答案，但仍然。

他们有自己的用例，其中任何一个都是明显的赢家。

例如：

1：https : //leetcode.com/problems/my-calendar-i TreeMap 是您正在查看的

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

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

于 2020-02-04T07:07:07.817 回答
0

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

于 2010-08-20T13:45:38.997 回答
0

当需要执行以下操作时，我发现 TreeMap 很有用：

  • 使用ceilingKey()找到大于等于某个值的最小/最小键
  • 使用floorKey()找到不等于某个值的最大/最大键

如果不需要上述内容，并且主要是为了快速选择检索最小值/最大值 - PriorityQueue 可能是首选。

于 2021-08-27T19:56:36.463 回答
0

埃里克森的回答清楚地说明了他们在时间复杂度上的差异。

在空间复杂度上，虽然堆和 TreeMap 都需要 O(n) 空间复杂度，但在实际程序中构建它们会占用不同的空间和精力。

假设你有一个数字数组，你可以用 O(n) 时间和恒定的额外空间构建一个堆。如果基于给定数组构建 TreeMap，则需要 O(nlogn) 时间和 O(n) 额外空间来完成此操作。

于 2022-02-25T03:14:16.387 回答