Что такое priority_queue в C++?

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

Основные характеристики:

• Реализация: Обычно строится поверх std::vector (контейнер по умолчанию) с использованием структуры данных "куча" (heap).
• Сложность операций:
  • push(): O(log n) — добавление элемента.
  • pop(): O(log n) — удаление верхнего элемента.
  • top(): O(1) — доступ к верхнему элементу.
• Интерфейс: Не предоставляет итераторов для обхода всех элементов, только доступ к вершине.

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

#include <queue>
#include <iostream>

int main() {
    // Очередь с приоритетом по умолчанию (максимальный элемент сверху)
    std::priority_queue<int> maxHeap;

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

    std::cout << "Top element: " << maxHeap.top() << 'n'; // 30

    // Извлечение всех элементов в порядке убывания
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << ' '; // Вывод: 30 20 10
        maxHeap.pop();
    }
    return 0;
}

Кастомизация: Можно изменить порядок и базовый контейнер, передав соответствующие параметры шаблона.

// Очередь с приоритетом, где сверху минимальный элемент
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);
std::cout << minHeap.top(); // 1