具有堆排序的优先级列表 (Java)

Question

我想知道是否存在使用堆排序方法的优先级列表的 Java 本机实现。如果没有，有没有推荐的替代方案？

Answer 1

PriorityQueue 的 javadoc 说：

"An unbounded priority queue based on a priority heap."

（Java 6 起）的源代码 PriorityQueue 有这样的注释：

"Priority queue represented as a balanced binary heap ..."

从技术上讲，这不是 Heapsort。然而，标准堆排序算法不适用于优先级队列：它是非增量的 (O(NlogN))。 PriorityQueue 所做的是增量的（每个队列插入 O(logN)）。

更多细节，请阅读源代码。评论很好