Получить доступ

В каком порядке выдаёт элементы итерация (for-each) по PriorityQueue?

MiddleКоллекции
Коротко

Итерация по PriorityQueue не отсортирована: куча гарантирует только «родитель ≤ детей». Отсортированный порядок даёт лишь повторный poll().

  • toString и for-each показывают массив кучи как есть
  • Отсортировать — poll() в цикле или скопировать и отсортировать
  • peek и poll возвращают минимум по Comparable или компаратору

А ещё Классическая ловушка: «распечатал очередь — порядок неправильный»

Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.

Попробуйте сами

Двоичная куча: вставка и извлечение

Подробно

PriorityQueue — бинарная куча в массиве: гарантируется лишь свойство кучи (родитель не больше детей), а не полный порядок. Поэтому for-each/toString выдают элементы как они лежат в массиве; отсортированную последовательность получают, многократно вызывая poll(). Это классическая ловушка «распечатал очередь и жду сортировки».

Что хотят услышать

  • Свойство кучи и почему итерация не отсортирована.
  • Как получить порядок.

Частые ошибки

  • Ждать отсортированный обход PriorityQueue.
  • Полагаться на порядок toString().

Проверьте себя

Один верный вариант. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✓В произвольном (лишь частично упорядоченном) порядке — отсортированный порядок гарантирован только при извлечении через poll()
  • ✗Строго по возрастанию — это же очередь с приоритетом
  • ✗В порядке вставки (FIFO)
  • ✗В обратном порядке вставки (LIFO)

Что спросят дальше

  • Какая сложность у poll() в куче?
  • Как получить отсортированный список из кучи?

Разбор темы

Связанные вопросы

Закрытая бета

Подсказки на собеседовании — в реальном времени

sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.

  • Промокод на 2 часа — сверх пробных 30 минут
  • Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
  • Прямая связь с разработчиком: что улучшить — сделаем