java的PriorityQueue的内置迭代器不以任何特定顺序遍历数据结构。为什么？ [英] The built-in iterator for java's PriorityQueue does not traverse the data structure in any particular order. Why?

问题描述

这直接来自 Java Docs ：

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

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

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

So basically, my PriorityQueue works fine, but printing it out to the screen using its own built in toString() method caused me to see this anomaly in action, and was wondering if someone could explain why it is that the iterator provided (and used internally) does not traverse the PriorityQueue in its natural order?

推荐答案

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

Because the underlying data structure doesn't support it. A binary heap is only partially ordered, with the smallest element at the root. When you remove that, the heap is reordered so that the next smallest element is at the root. There is no efficient ordered traversal algorithm so none is provided in Java.

这篇关于java的PriorityQueue的内置迭代器不以任何特定顺序遍历数据结构。为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！