Как работает структура данных priority_queue в C++?

priority_queue в C++ — это контейнерный адаптер, предоставляющий интерфейс очереди с приоритетами. Он работает следующим образом:

1. Основа: По умолчанию priority_queue реализована поверх вектора (std::vector) и использует кучу (heap) для управления своими элементами. В частности, std::make_heap, std::push_heap и std::pop_heap используются для поддержания свойства кучи.

2. Куча: Поддерживается свойство максимальной кучи (max-heap) по умолчанию. Это означает, что наибольший элемент всегда находится в корне кучи.

3. Вставка (push):

   • Новый элемент добавляется в конец базового контейнера (например, вектора).
   • Затем вызывается std::push_heap, чтобы восстановить свойство кучи. Элемент "поднимается" вверх по дереву кучи до тех пор, пока не окажется на правильной позиции относительно своих родителей и потомков.

4. Извлечение (pop):

   • Самый приоритетный (наибольший в случае max-heap) элемент находится в корне (на первой позиции в плоском представлении вектора).
   • Чтобы удалить его, последний элемент базового контейнера переносится в корень.
   • Реальный корень (который мы хотим удалить) сохраняется.
   • Размер базового контейнера уменьшается.
   • Затем вызывается std::pop_heap, которая перемещает новый корневой элемент ("проваливает" его) вниз по дереву, меняя местами с наибольшим из своих потомков до тех пор, пока свойство кучи не будет восстановлено.
   • Остается только извлечь сохраненный ранее максимальный элемент.

5. Доступ к верхнему элементу (top): Возвращает ссылку на элемент в корне кучи (наиболее приоритетный). Эта операция не изменяет контейнер.

6. Порядок: По умолчанию используется std::less для сравнения элементов, что приводит к max-heap (наибольший элемент имеет наивысший приоритет). Можно указать пользовательский компаратор (например, std::greater для min-heap) и базовый контейнер.

Пример использования (max-heap):

cpp

Пример использования (min-heap):

cpp

Сложность операций:

Где N — количество элементов в очереди.