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 回答