Что такое структура данных priority_queue?

priority_queue — адаптер контейнера из стандартной библиотеки C++, который предоставляет функциональность очереди с приоритетами. Элементы извлекаются в порядке их приоритета (по умолчанию, наибольший элемент имеет наивысший приоритет). По сути, это обертка над другим контейнером (по умолчанию std::vector), которая использует алгоритмы кучи (std::make_heap, std::push_heap, std::pop_heap) для поддержания структуры кучи внутри базового контейнера.

Ключевые особенности:

• Приоритет: Элементы извлекаются согласно их приоритету. По умолчанию используется std::less для определения приоритета, что означает наибольший элемент считается имеющим наивысший приоритет (макс-куча). Можно изменить порядок, предоставив другой компаратор, например, std::greater для мин-кучи.
• Адаптер: priority_queue не является самостоятельным контейнером, а адаптирует другой базовый контейнер (обычно std::vector, но может быть и другой, например std::deque), предоставляя интерфейс очереди с приоритетами.
• Куча: Внутренне реализована с использованием кучи, что обеспечивает логарифмическую сложность для операций вставки и извлечения.
• Неупорядоченный доступ: Не предоставляет произвольного доступа к элементам. Доступны только операции вставки (push), извлечения элемента с наивысшим приоритетом (pop) и просмотра элемента с наивысшим приоритетом (top).

Основные операции:

Пример использования:

cpp

Используется в алгоритмах, где необходимо постоянно извлекать элемент с наивысшим (или наименьшим) приоритетом, например, алгоритм Дейкстры, алгоритм Прима или в задачах моделирования событий.