Java 的 PriorityQueue 的内置迭代器不会以任何特定顺序遍历数据结构。为什么？

java priority-queue

2022-09-02 23:34:15

这直接来自Java文档：

此类及其迭代器实现集合和迭代器接口的所有可选方法。方法迭代器（）中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用 Arrays.sort（pq.toArray（））。

所以基本上，我的PriorityQueue工作正常，但是使用它自己内置的toString（）方法将其打印到屏幕上，使我看到这种异常现象，并且想知道是否有人可以解释为什么提供的迭代器（并在内部使用）不以自然顺序遍历PriorityQueue？

答案 1

因为基础数据结构不支持它。二进制堆仅部分排序，最小的元素位于根目录。删除该元素时，将对堆进行重新排序，以便下一个最小的元素位于根目录。没有有效的有序遍历算法，因此Java中没有提供任何算法。

答案 2

优先级队列是使用二进制堆实现的。堆不是已排序的结构，它是部分排序的。每个元素都有一个与之关联的“优先级”。使用堆实现优先级队列，它将始终在堆的根节点中具有最高优先级的元素。因此，在优先级队列中，具有高优先级的元素先于具有低优先级的元素提供服务。如果两个元素具有相同的优先级，则根据它们在队列中的顺序提供服务。每次删除元素后都会更新堆，以维护堆属性