何时应该在优先级队列上使用树状图，反之亦然？

java priority-queue treemap

2022-08-31 20:52:31

似乎它们都允许您检索最小值，这是我Prim算法所需的，并强制我删除并重新插入键以更新其值。使用一个比另一个有什么好处吗，不仅仅是在这个例子中，而是一般来说？

答案 1

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

树更有条理，需要更多的计算来维持这种组织。但是，如果您需要访问任何密钥，而不仅仅是最小值，则堆将不够，并且树的额外开销是合理的。

答案 2

我想指出2个区别（这可能与Java中PriorityQueue和TreeSet之间的差异更相关？因为这个问题被认为是这个问题的dup）。

（1）优先级队列可以有重复项，而 TreeSet 不能有 dups。因此，在Treeset中，如果您的比较器认为2个元素相等，TreeSet将只保留这2个元素中的一个，并丢弃另一个元素。

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

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