Vai jūs zināt konteineru kā kaudzi?

Jā, pazīstu. Kupols (heap) ir specializēta koka struktūra, kas atbilst kupola noteikumam: katra virsotnei tās vērtība ir jābūt ne mazāka (vai ne lielāka) par tās bērnu vērtībām.

Atšķir:

• Maksimālais kupols (Max-heap): Vecāka virsotnes vērtība vienmēr ir lielāka vai vienāda ar tās bērnu vērtībām. Lielākais elements atrodas saknē.
• Minimālais kupols (Min-heap): Vecāka virsotnes vērtība vienmēr ir mazāka vai vienāda ar tās bērnu vērtībām. Mazākais elements atrodas saknē.

Populāra kupola realizācija ir binārais kupols, kas parasti tiek attēlots kā masīvs. Saistība starp vecāku un bērniem tiek noteikta pēc masīva indeksiem:

• Kreisais bērns i indeksā ir 2*i + 1.
• Labais bērns i indeksā ir 2*i + 2.
• Vecāks i indeksā ir (i - 1) / 2.

Galvenās operācijas un to laika sarežģītība (bināram kupolam):

Operācija	Laika sarežģītība
Kupola izveide	O(n)
Elementa pievienošana	O(log n)
Maksimuma/minimuma noņemšana	O(log n)
Augšējās virsotnes apskate	O(1)

Kupola pielietojums:

• Prioritātes rindu realizācija.
• Sakārtošanas algoritms — kupola kārtošana (Heap Sort).
• Grafu būvniecības algoritmi (piemēram, Dijkstra, Prim).

C++ standarta bibliotēka nodrošina std::priority_queue, kas ir konteineru adapteris un pēc noklusējuma izmanto std::vector kā galveno konteineru un realizē maksimālo kupolu.

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

int main() {
    // Prioritātes rinda (pēc noklusējuma — maksimālais kupols)
    std::priority_queue<int> max_heap;

    // Elementu pievienošana
    max_heap.push(10);
    max_heap.push(30);
    max_heap.push(20);
    max_heap.push(5);

    // Elementu izņemšana (dilstošā secībā)
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " "; // Skats uz virsotni
        max_heap.pop(); // Noņemšana
    }
    std::cout << std::endl;

    // Minimālais kupols
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    min_heap.push(10);
    min_heap.push(30);
    min_heap.push(20);
    min_heap.push(5);

    // Elementu izņemšana (augošā secībā)
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " ";
        min_heap.pop();
    }
    std::cout << std::endl;

    return 0;
}