Порядок элементов в PriorityQueue

Рейтинг: 1Ответов: 2Опубликовано: 11.01.2023

Создается PriorityQueue из элементов Integer с использованием компаратора

IntComparator intComparator = new IntComparator();
PriorityQueue<Integer> integerPriorityQueue2 = new PriorityQueue<>(intComparator);

integerPriorityQueue2.add(4);
integerPriorityQueue2.add(3);
integerPriorityQueue2.add(5);
integerPriorityQueue2.add(9);
integerPriorityQueue2.offer(1);

Компаратор:

@Override
public int compare(Integer o1, Integer o2) {
    return (o1 - o2);
}

Проходим по полученной коллекции итератором:

System.out.print("IntegerPriorityQueue2. Using an iterator: ");
Iterator<Integer> iterator2 = integerPriorityQueue2.iterator();
while(iterator2.hasNext()) {
    System.out.print(iterator2.next() + ", ");
}
System.out.println("");

Ожидание:

1, 3, 4, 5, 9

Реальность:

1, 3, 5, 9, 4

В чем причина?

java коллекции итераторы очередь
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Если нужно вывести содержимое приоритетной очереди в желаемом порядке, вместо итератора следует воспользоваться циклом, в котором элементы вычитываются при помощи метода poll:

while (!integerPriorityQueue2.isEmpty()) {
    System.out.print(integerPriorityQueue2.poll() + "  ");
}

Вывод:

1  3  4  5  9

Для гарантированной сортировки следует либо воспользоваться реализацией SortedSet типа TreeSet, или же содержимое очереди придётся сортировать отдельно, например, как указано в документации: If you need ordered traversal, consider using Arrays.sort(pq.toArray()). или при помощи стрима:

integerPriorityQueue2.stream().sorted().forEach(System.out::println);

Также следует заметить, что данная реализация IntComparator не отличается по сути от обычной сортировки целых чисел в порядке возрастания, которая и так применяется в приоритетной очереди по умолчанию.

К тому же данная реализация содержит потенциальное целочисленное переполнение, т.е. по сути некорректна, и данный класс лучше было бы заменить на ссылку на метод Integer::compare:

PriorityQueue<Integer> integerPriorityQueueAsc = new PriorityQueue<>(Integer::compare); // по возрастанию

или обратным компаратором Comparator.reverseOrder() для сортировки по убыванию:

PriorityQueue<Integer> integerPriorityQueueDesc = new PriorityQueue<>(Comparator.reverseOrder()); // по убыванию
▲ 0

Приоритетная очередь не упорядоченная коллекция. Если вам повезёт - в большинстве реализаций минимум будет на первом элементе.

PriorityQueue:

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()).

Статья Двоичная куча объясняет как устроена в большинстве случаев приоритетная очередь. Здесь описана очередь максимумов, а очередь в Java - очередь минимумов. В остальном описание верное.