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

Question

似乎它们都让你检索最小值,这是我对Prim算法所需要的,并强制我删除并重新插入一个键来更新它的值.使用一个优于另一个是否有任何优势,不仅仅是这个例子,但一般来说？

Answer 1

一般来说,使用堆来跟踪最小元素的工作量较少.

树更有条理,需要更多计算才能维护该组织.但是如果你需要访问任何密钥,而不仅仅是最小密钥,那么堆就不够了,并且树的额外开销是合理的.

Answer 2

完全同意Erickson关于该优先级队列只给出最小/最大元素.

此外,由于优先级队列在维护数据的总顺序方面不太强大,因此在某些特殊情况下具有优势.如果要跟踪M数组中最大的元素N,时间复杂度将是O(N*LogM)空间复杂度O(M).但是如果你在地图中这样做,时间的复杂性就是O(N*logN)空间O(N).这是非常基础的,而在某些情况下我们必须使用优先级队列,例如,M它只是一个常数,如10.

Answer 3

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

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

Answer 4

关于它的经验法则是：

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

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

Answer 5

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

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

Answer 6

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

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

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

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