Kas ir datu struktūra priority_queue?

priority_queue — C++ standarta bibliotēkas kontaineru adapteris, kas nodrošina prioritātes rindu funkcionalitāti. Elementi tiek izvilkti pēc to prioritātes (pēc noklusējuma, lielākais elements ir ar augstāko prioritāti). Būtībā tas ir pārklājums pār citu konteineru (parasti std::vector), kas izmanto kaudzes algoritmus (std::make_heap, std::push_heap, std::pop_heap), lai uzturētu kaudzes struktūru iekšējā konteinerā.

Galvenās iezīmes:

• Prioritāte: Elementi tiek izvilkti saskaņā ar to prioritāti. Pēc noklusējuma tiek izmantots std::less, kas nozīmē, ka lielākais elements tiek uzskatīts par ar augstāko prioritāti (maks-heap). Prioritāti var mainīt, nodrošinot citu komparatoru, piemēram, std::greater min-heap gadījumā.
• Adapteris: priority_queue nav patstāvīgs konteineris, bet adaptē citu pamata konteineru (parasti std::vector, bet var būt arī cits, piemēram, std::deque), nodrošinot prioritātes rindu interfeisu.
• Kaudze: Iekšēji realizēta ar kaudzes struktūru, kas nodrošina logaritmisku sarežģītību ievietošanas un izvilkšanas operācijām.
• Nepārtraukta piekļuve: Nepiedāvā brīvu piekļuvi elementiem. Pieejamas tikai operācijas ievietošanai (push), elementa izvilkšanai ar augstāko prioritāti (pop) un skatīšanai uz elementu ar augstāko prioritāti (top).

Galvenās operācijas:

Operācija	Apraksts	Sarežģītība (vidējā / sliktākajā gadījumā)
push	Ievieto elementu ar norādītu prioritāti.	O(log N)
pop	Noņem elementu ar augstāko prioritāti.	O(log N)
top	Atgriež nemainīgu atsauci uz elementu ar augstāko prioritāti.	O(1)
empty	Pārbauda, vai rinda ir tukša.	O(1)
size	Iegūst elementu skaitu rindā.	O(1)

Piemērs izmantošanai:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // lai izmantotu std::greater

int galvenais() {
    // Maks-heap (pēc noklusējuma)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Maks-heap elementi (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Min-heap (izmantojot 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 << "Min-heap elementi (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Tas tiek izmantots algoritmos, kur ir nepieciešams pastāvīgi izvilkt elementu ar augstāko (vai zemāko) prioritāti, piemēram, Dijkstra algoritmā, Prim algoritmā vai notikumu modelēšanas uzdevumos.