Встроенный итератор для Java PriorityQueue не пересекает структуру данных в каком-либо конкретном порядке. Зачем?
Это прямо из Документов Java:
Этот класс и его итератор реализуют все необязательные методы интерфейсов Collection и Iterator. Итератор, предоставленный в методе iterator(), не гарантирует прохождение элементов очереди с приоритетами в любом конкретном порядке. Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort(pq.toArray()).
Так что в основном мой PriorityQueue работает нормально, но распечатка его на экран с использованием его собственного встроенного метода toString() заставила меня увидеть эту аномалию в действии, и мне было интересно, может ли кто-нибудь объяснить, почему именно итератор предоставил (и использовал внутренне) не пересекает PriorityQueue в его естественном порядке?
5 ответов
Потому что основная структура данных не поддерживает это. Бинарная куча только частично упорядочена, с наименьшим элементом в корне. Когда вы удаляете это, куча переупорядочивается так, чтобы следующий наименьший элемент находился в корне. Эффективного алгоритма упорядоченного обхода не существует, поэтому в Java его нет.
PriorityQueues реализуются с использованием двоичной кучи. Куча не является отсортированной структурой, и она частично упорядочена. С каждым элементом связан "приоритет". Используя кучу для реализации очереди с приоритетами, она всегда будет иметь элемент с наивысшим приоритетом в корневом узле кучи. поэтому в очереди с приоритетами элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом. Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди. Куча обновляется после каждого удаления элементов, чтобы сохранить свойство кучи
На первый взгляд, это, вероятно, обход данных в порядке их хранения. Чтобы минимизировать время для вставки элемента в очередь, обычно он не хранит все элементы в отсортированном порядке.
Ну, как говорит Javadoc, так оно и было реализовано. Приоритетная очередь, вероятно, использует двоичную кучу в качестве базовой структуры данных. Когда вы удаляете элементы, куча переупорядочивается, чтобы сохранить свойство кучи.
Во-вторых, неразумно связывать конкретную реализацию (форсируя отсортированный порядок). С текущей реализацией вы можете проходить ее в любом порядке и использовать любую реализацию.
Двоичные кучи являются эффективным способом реализации приоритетных очередей. Единственная гарантия порядка, который делает куча, состоит в том, что элемент сверху имеет наивысший приоритет (может быть, он является "самым большим" или "самым маленьким" в соответствии с некоторым порядком). Куча - это бинарное дерево, которое имеет свойства: свойство Shape: дерево заполняется сверху вниз слева направо. Упорядочить свойство: элемент в любом узле больше (или меньше, если наименьший имеет высший приоритет), чем его два дочерних узла. Когда итератор посещает все элементы, он, вероятно, делает это в обход уровня порядка, то есть он посещает каждый узел на каждом уровне по очереди, прежде чем перейти к следующему уровню. Поскольку предоставляется единственная гарантия порядка, в которой узел имеет более высокий приоритет, чем его дочерние элементы, узлы на каждом уровне не будут иметь определенного порядка.