Каква е структурата данни 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).

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

Операция	Описание	Сложност (средна/най-лоша)
push	Вмъква елемент с даден приоритет.	O(log N)
pop	Премахва елемент с най-висок приоритет.	O(log N)
top	Връща константна препратка към елемента с най-висок приоритет.	O(1)
empty	Проверява дали опашката е празна.	O(1)
size	Получава броя на елементите в опашката.	O(1)

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

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // за std::greater

int main() {
    // Макс-купа (по подразбиране)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Елементи на макс-купа (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Мин-купа (използвайки std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Елементи на мин-купа (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

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