什么时候应该在PriorityQueue上使用TreeMap，反之亦然？
似乎他们都让你检索最小值，这是我对Prim算法所需要的，并强制我删除并重新插入一个键来更新它的值。 使用一个优于另一个是否有任何优势，不仅仅是这个例子，但一般来说？
一般来说，使用堆来跟踪最小元素的工作量较少。
树更有条理，并且需要更多计算来维护该组织。 但是如果你需要访问任何密钥，而不仅仅是最小的密钥，那么堆就不够了，并且树的额外开销是合理的。
完全同意Erickson关于该优先级队列只给出最小/最大元素。
此外，由于优先级队列在维护数据的总顺序方面不太强大，因此在某些特殊情况下具有优势。 如果要跟踪N个数组中最大的M元素，则时间复杂度为O(N*LogM) ，空间复杂度为O(M) 。 但如果你在地图中进行，时间复杂度为O(N*logN) ，空间为O(N) 。 这是非常基本的，而在某些情况下我们必须使用优先级队列，例如M只是一个常数，如10。
我想指出有两点不同（这可能与Java中的PriorityQueue和TreeSet之间的差异更相关？因为该问题被认为是这个问题的重复）。
（1）PriorityQueue可以有重复项，因为TreeSet不能有重复项。 所以在Treeset中，如果你的比较器认为2个元素相等，那么TreeSet将只保留这两个元素中的一个并扔掉另一个元素。
（2）TreeSet迭代器以排序顺序遍历集合，而PriorityQueue迭代器不按排序顺序遍历。 对于PriorityQueue如果要按排序顺序获取项目，则必须通过反复调用remove（）来销毁队列。
我假设讨论仅限于Java对这些数据结构的实现。
关于它的经验法则是：
TreeMap按顺序维护所有元素。 （如此直观地说，构建它需要时间）
PriorityQueue仅限隔离最小值或最大值。 它更便宜但function更低。
其中一个区别是remove（Object）和contains（Object）在基于普通堆的PriorityQueue（如Oracle）中是线性O（N），但是对于TreeSet / Map是O（log（N））。
因此，如果您有大量元素并执行大量删除（Object）或包含（Object），那么TreeSet / Map可能会更快。
这一切都取决于你想要达到的目标。 在您选择其中一个之前，请考虑以下要点。
- PriorityQueue允许重复（即具有相同的优先级），而TreeMap不允许。
- PriorityQueue的复杂度是O（n）（当增加其大小时），而TreeMap的复杂度是O（logn）（因为它基于红黑树）
- PriorityQueue基于Array，而TreeMap节点彼此链接，因此包含PriorityQueue的方法将花费O（n）时间，而TreeMap将花费O（logn）时间。
这取决于您如何实现优先级队列。 根据Cormen的第二版第二版，最快的结果是Fibonacci Heap。