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

问题描述

这直接来自 Java 文档:

该类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法.方法 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屋！