Ismered a halomhoz hasonló konténert?

Igen, ismerem. A halom (heap) egy speciális fa, amely megfelel a halom szabályának: minden csúcs értékének nagyobbnak vagy egyenlőnek kell lennie, mint bármelyik leszármazott értéke.

Különböző típusai:

• Max-heap: A szülő csúcs értéke mindig nagyobb vagy egyenlő, mint a leszármazottaké. A legnagyobb elem a gyökérben található.
• Min-heap: A szülő csúcs értéke mindig kisebb vagy egyenlő, mint a leszármazottaké. A legkisebb elem a gyökérben található.

Egy gyakori megvalósítás a bináris halom, amelyet általában tömbként ábrázolnak. A szülő-gyermek kapcsolat a tömb indexei alapján határozható meg:

• Az i indexű elem bal gyermekének indexe 2*i + 1.
• Az i indexű elem jobb gyermekének indexe 2*i + 2.
• Az i indexű elem szülőjének indexe (i - 1) / 2.

A fő műveletek és azok időbeli összetettsége (bináris halom esetén):

Művelet	Időbeli összetettség
Halom létrehozása	O(n)
Elem beszúrása	O(log n)
Maximum/minimum törlése	O(log n)
Maximum/minimum kivétele	O(log n)
Csúcs megtekintése	O(1)

A halom alkalmazásai:

• Prioritási sorok megvalósítása.
• Halom rendezés (Heap Sort).
• Grafépítő algoritmusok (pl. Dijkstra, Prim).

A C++ szabványos könyvtárában a std::priority_queue egy konténeradapter, amely alapértelmezés szerint a std::vector-t használja, és maximális halmot valósít meg.

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

int main() {
    // Prioritási sor létrehozása (alapértelmezett: maximális halom)
    std::priority_queue<int> max_heap;

    // Elemek hozzáadása
    max_heap.push(10);
    max_heap.push(30);
    max_heap.push(20);
    max_heap.push(5);

    // Elemek kivétele (csökkenő sorrendben)
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " "; // Csúcs megtekintése
        max_heap.pop(); // Csúcs eltávolítása
    }
    std::cout << std::endl;

    // Minimális halom létrehozása
    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);

    // Elemek kivétele (növekvő sorrendben)
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " ";
        min_heap.pop();
    }
    std::cout << std::endl;

    return 0;
}