java PriorityQueue 的内置迭代器不会以任何特定顺序遍历数据结构。为什么？
这直接来自 Java文档：
此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。 方法 iterator() 中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用 Arrays.sort(pq.toArray())。
所以基本上，我的 PriorityQueue 工作正常，但是使用它自己的内置 toString() 方法将其打印到屏幕上使我看到了这种异常现象，并且想知道是否有人可以解释为什么迭代器提供（并使用内部）不按其自然顺序遍历 PriorityQueue？
This is straight from the Java Docs:
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()).
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
因为底层数据结构不支持。二叉堆仅是部分有序的，最小的元素位于根。当您删除它时，堆会重新排序，以便下一个最小的元素位于根。 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.
PriorityQueues 使用二进制堆实现。
堆不是排序结构，而是部分排序的。每个元素都有一个与之相关的“优先级”。使用堆来实现优先级队列，它将始终在堆的根节点中具有最高优先级的元素。因此，在优先级队列中，优先级高的元素先于优先级低的元素被服务。如果两个元素具有相同的优先级，则根据它们在队列中的顺序提供服务。每次删除元素后都会更新堆以维护堆属性
PriorityQueues are implemented using binary heap.
A heap is not a sorted structure and it is partially ordered. Each element has a “priority” associated with it. Using a heap to implement a priority queue, it will always have the element of highest priority in the root node of the heap. so in a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. Heap is updated after each removal of elements to maintain the heap property
乍一看，它可能是按照数据存储的顺序遍历数据。为了最大限度地减少在队列中插入项目的时间，它通常不会按排序顺序存储所有项目。
At first guess, it's probably traversing the data in the order in which it's stored. To minimize the time to insert an item in the queue, it doesn't normally store all the items in sorted order.
嗯，正如 Javadoc 所说，这就是它的实现方式。优先级队列可能使用二进制堆作为底层数据结构。当您删除项目时，堆将重新排序以保留堆属性。
其次，绑定特定的实现（强制排序顺序）是不明智的。使用当前的实现，您可以自由地以任何顺序遍历它并使用任何实现。
Well, as the Javadoc says, that's how it's been implemented. The priority queue probably uses a binary heap as the underlying data structure. When you remove items, the heap is reordered to preserve the heap property.
Secondly, it's unwise to tie in a specific implementation (forcing a sorted order). With the current implementation, you are free to traverse it in any order and use any implementation.
二叉堆是实现优先级队列的有效方法。关于堆的顺序的唯一保证是顶部的项目具有最高优先级（根据某种顺序，它可能是“最大”或“最小”）。
堆是一棵二叉树，具有以下属性：
Shape属性：树从上到下从左到右填充
顺序属性：任何节点上的元素都比其两个子节点大（如果最小的优先级最高，则更小）。
当迭代器访问所有元素时，它可能以层序遍历的方式进行，即在进入下一层之前依次访问每个层中的每个节点。由于对顺序的唯一保证是节点比其子节点具有更高的优先级，因此每个级别中的节点将没有特定的顺序。
Binary heaps are an efficient way of implementing priority queues. The only guarantee about order that a heap makes is that the item at the top has the highest priority (maybe it is the "biggest" or "smallest" according to some order).
A heap is a binary tree that has the properties:
Shape property: the tree fills up from top to bottom left to right
Order prperty: the element at any node is bigger (or smaller if smallest has highest priority) than its two children nodes.
When the iterator visits all the elements it probably does so in a level-order traversal, i.e. it visits each node in each level in turn before going on to the next level. Since the only guarantee about order that is made that a node has a higher priority than its children, the nodes in each level will be in no particular order.