似乎它们都可以让您检索最小值,这是 Prim 算法所需的,并强制我删除并重新插入密钥以更新其值。使用一个比另一个有什么优势,不仅仅是这个例子,而且一般来说?
10 回答
一般来说,使用堆只跟踪最小元素的工作量较少。
一棵树更有条理,它需要更多的计算来维持这种组织。但是,如果您需要访问任何键,而不仅仅是最小值,那么堆是不够的,树的额外开销是合理的。
我想指出两个差异(这可能与 Java 中 PriorityQueue 和 TreeSet 之间的差异更相关?因为该问题被视为该问题的重复)。
(1) PriorityQueue 可以有重复,而 TreeSet 不能有重复。因此,在 Treeset 中,如果您的比较器认为 2 个元素相等,则 TreeSet 将仅保留这 2 个元素中的一个并丢弃另一个元素。
(2) TreeSet 迭代器按排序顺序遍历集合,而 PriorityQueue 迭代器不按排序顺序遍历。对于 PriorityQueue 如果要按排序顺序获取项目,则必须通过重复调用 remove() 来销毁队列。
我假设讨论仅限于 Java 对这些数据结构的实现。
完全同意 Erickson 在该优先级队列上的观点只为您提供最小/最大元素。
此外,由于优先级队列在维护数据总顺序方面的功能较弱,因此在某些特殊情况下具有优势。如果要跟踪M
数组中的最大元素N
,时间复杂度为O(N*LogM)
,空间复杂度为O(M)
。但是如果你在地图上做,时间复杂度是O(N*logN)
,空间是O(N)
。这是非常基本的,而在某些情况下我们必须使用优先级队列,例如M
只是一个像 10 这样的常数。
关于它的经验法则是:
TreeMap 有序地维护所有元素。(所以直观地说,构建它需要时间)
PriorityQueue 只保证最小值或最大值。它更便宜,但功能更弱。
这一切都取决于您想要实现的目标。以下是在您选择其中一个之前要考虑的要点。
- PriorityQueue 允许重复(即具有相同优先级),而 TreeMap 不允许。
- PriorityQueue 的复杂度是 O(n)(当它增加它的大小时),而 TreeMap 的复杂度是 O(logn)(因为它是基于红黑树)
- PriorityQueue 是基于数组的,而 TreeMap 中的节点是相互链接的,因此包含 PriorityQueue 的方法需要 O(n) 时间,而 TreeMap 需要 O(logn) 时间。
区别之一是 remove(Object) 和 contains(Object) 在基于普通堆的 PriorityQueue(如 Oracle 的)中是线性 O(N),但对于 TreeSet/Map 是 O(log(N))。
因此,如果您有大量元素并执行大量删除(对象)或包含(对象),那么 TreeSet/Map 可能会更快。
这取决于您如何实现优先队列。根据 Cormen 的书第 2 版,最快的结果是斐波那契堆。
当需要执行以下操作时,我发现 TreeMap 很有用:
- 使用ceilingKey()找到大于等于某个值的最小/最小键
- 使用floorKey()找到不等于某个值的最大/最大键
如果不需要上述内容,并且主要是为了快速选择检索最小值/最大值 - PriorityQueue 可能是首选。
埃里克森的回答清楚地说明了他们在时间复杂度上的差异。
在空间复杂度上,虽然堆和 TreeMap 都需要 O(n) 空间复杂度,但在实际程序中构建它们会占用不同的空间和精力。
假设你有一个数字数组,你可以用 O(n) 时间和恒定的额外空间构建一个堆。如果基于给定数组构建 TreeMap,则需要 O(nlogn) 时间和 O(n) 额外空间来完成此操作。