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

Question

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

这是直接从Java文档:

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

因此，基本上，我的PriorityQueue工作得很好，但是使用它自己内置的toString()方法将它打印到屏幕上，使我看到了这个异常现象，并想知道是否有人能解释为什么提供的迭代器(并在内部使用)不按照其自然顺序遍历PriorityQueue？

Answer 1

因为底层数据结构不支持它。二进制堆仅部分有序，根处是最小的元素。当您删除它时，堆将被重新排序，以便下一个最小的元素位于根。由于没有有效的有序遍历算法，所以Java中没有提供有效的有序遍历算法。

Answer 2

二进制堆是实现优先级队列的有效方法。堆所做的顺序的唯一保证是顶部的项具有最高的优先级(根据某些顺序，它可能是“最大的”或“最小的”)。堆是具有属性：Shape属性的二叉树：树从上到下，从左到右顺序填充：任何节点上的元素都比其两个子节点大(或者最小的元素具有最高优先级)。当迭代器访问所有元素时，它很可能是以逐级遍历的方式进行访问的，也就是说，在进入下一个级别之前，它依次访问每个级别中的每个节点。由于唯一保证一个节点比其子节点具有更高优先级的顺序，因此每个级别上的节点都不会有特定的顺序。