Как работает структура данных 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):

#include <queue>
#include <vector>
#include <iostream>

// Пример использования priority_queue (max-heap по умолчанию)
int main() {
    std::priority_queue<int> pq; // Основан на std::vector<int> и использует std::less<int>

    pq.push(10);
    pq.push(30);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // Доступ к наибольшему элементу
        pq.pop(); // Удаление наибольшего элемента
    }
    // Вывод: 30 20 10
    return 0;
}

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

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // Для std::greater

// Пример использования priority_queue (min-heap)
int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // Доступ к наименьшему элементу
        pq.pop(); // Удаление наименьшего элемента
    }
    // Вывод: 10 20 30
    return 0;
}

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

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