Kā darbojas datu struktūra priority_queue C++?

priority_queue C++-ā ir konteineru pielāgotājs, kas nodrošina prioritāšu rindu interfeisu. Tas darbojas šādi:

1. Pamatā: Parasti priority_queue ir realizēts virs vektora (std::vector) un izmanto kaudzi (heap), lai pārvaldītu savus elementus. Konkrēti, tiek izmantoti std::make_heap, std::push_heap un std::pop_heap, lai uzturētu kaudzes īpašības.

2. Kaudze: Sākotnēji tiek uzturēta maksimālās kaudzes (max-heap) īpašība. Tas nozīmē, ka lielākais elements vienmēr atrodas kaudzes augšā.

3. Ievietošana (push):

   • Jauns elements tiek pievienots galvenā konteineru (piemēram, vektora) beigās.
   • Tad tiek izsaukts std::push_heap, lai atjaunotu kaudzes īpašības. Elements "pacēlies" augšup pa kaudzes koku līdz atrodas pareizajā pozīcijā attiecībā pret vecākiem un bērniem.

4. Izņemšana (pop):

   • Prioritātes elements (vislielākais gadījumā max-heap) atrodas kaudzes augšā (pirmā pozīcija vektorā).
   • Lai to izņemtu, pēdējais galvenā konteineru elements tiek pārvietots uz augšu.
   • Reālais elements, ko vēlamies izņemt, tiek saglabāts.
   • Galvenā konteineru izmērs tiek samazināts.
   • Tad tiek izsaukts std::pop_heap, kas pārvieto jauno galveno elementu uz leju pa kaudzes koku, mainot vietām ar lielāko no saviem bērniem, līdz kaudzes īpašības ir atjaunotas.
   • Paliek tikai izņemt iepriekš saglabāto maksimālo elementu.

5. Piekļuve virsējam elementam (top): Atgriež atsauci uz kaudzes virsējo elementu (visprioritātes). Šī operācija nemaina konteineru.

6. Kārtība: Pēc noklusējuma tiek izmantots std::less salīdzināšanai, kas rada max-heap (vislielākais elements ir ar augstāko prioritāti). Var norādīt lietotāja definētu salīdzinātāju (piemēram, std::greater min-heap) un galveno konteineru.

Piemērs (max-heap):

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

// Piemērs, izmantojot priority_queue (noklusējuma max-heap)
int main() {
    std::priority_queue<int> pq; // balstīts uz std::vector<int> un izmanto std::less<int>

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

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // piekļuve lielākajam elementam
        pq.pop(); // lielākā elementa izņemšana
    }
    // Izvade: 30 20 10
    return 0;
}

Piemērs (min-heap):

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

// Piemērs, izmantojot 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() << " "; // piekļuve mazākajam elementam
        pq.pop(); // mazākā elementa izņemšana
    }
    // Izvade: 10 20 30
    return 0;
}

Operāciju sarežģītība:

Operācija	Vidējā sarežģītība	Sliktākajā gadījumā
push	O(log N)	O(log N)
pop	O(log N)	O(log N)
top	O(1)	O(1)
empty/size	O(1)	O(1)

Kur N — elementu skaits rindā.