На какой структуре данных основана очередь с приоритетом (priority_queue)?

Очередь с приоритетом в стандартной библиотеке C++ (std::priority_queue) по умолчанию основана на структуре данных куча (heap). Конкретно — на максимальной куче (max-heap) по умолчанию, где наибольший элемент всегда находится в корне.

Это позволяет эффективно выполнять две ключевые операции очереди с приоритетом:

• Извлечение элемента с наивысшим приоритетом (обычно top() + pop()): O(log N)
• Добавление нового элемента (push()): O(log N)

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

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

int main() {
    // Создание priority_queue с использованием вектора как базового контейнера
    std::priority_queue<int, std::vector<int>, std::less<int>> pq; // less<int> для max-heap

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

    std::cout << "Top element: " << pq.top() << std::endl; // 30

    pq.pop(); // Удалить 30

    std::cout << "Top element after pop: " << pq.top() << std::endl; // 20

    return 0;
}