max-heap

max-heap (tsz. max-heaps)

1. (informatika) A max-heap (vagy maximum prioritású kupac) egy bináris faalapú adatszerkezet, amely minden csomópontra teljesíti a következő tulajdonságot:

Bármely csomópont értéke nagyobb vagy egyenlő a gyerekeinek értékénél.

Ez azt jelenti, hogy a legnagyobb érték mindig a gyökérben van.

A max-heap egy:

• Teljes bináris fa: minden szint teljesen kitöltött balról jobbra.
• Tömbként tárolt: nem pointerekkel, hanem egy vektorban, ahol a szülő-gyerek kapcsolatok indexek alapján számolhatók.

Egy heap pozícióhoz:

Egy max-heap lehet például így:

        100
       /   \
     50     30
    / \    / \
  20  10  5   1

Tömbként tárolva:

1. Beszúrjuk az x elemet a tömb végére.
2. Felcseréljük a szülőjével, amíg nagyobb nála → “bubble up” vagy “heapify up”.

1. A gyökeret (legnagyobb elem) eltávolítjuk.
2. Az utolsó elemmel helyettesítjük a gyökeret.
3. Lefelé rendezünk → “heapify down”.

class MaxHeap {
    vector<int> heap;

    void heapifyDown(int i) {
        int n = heap.size();
        int largest = i;
        int l = 2*i + 1;
        int r = 2*i + 2;

        if (l < n && heap > heap) largest = l;
        if (r < n && heap > heap) largest = r;

        if (largest != i) {
            swap(heap, heap);
            heapifyDown(largest);
        }
    }

    void heapifyUp(int i) {
        while (i > 0 && heap > heap) {
            swap(heap, heap);
            i = (i - 1) / 2;
        }
    }

public:
    void insert(int val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) throw runtime_error("Empty heap");
        int maxVal = heap;
        heap = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return maxVal;
    }

    int getMax() const {
        if (heap.empty()) throw runtime_error("Empty heap");
        return heap;
    }
};

• Prioritási sorok (priority queues)
• Ütemezés (CPU process scheduler)
• Huffman-kódolás
• K-mező legnagyobb értékei
• Heapsort algoritmus

• Építs max-heapet az adatokból.
• Iteratív lépésekben:
  • Cseréld a gyökeret az utolsó elemmel.
  • “Kivonod” az utolsó elemet (max).
  • heapifyDown a gyökérre.
• Eredmény: rendezett (növekvő) sorozat.

Időkomplexitás: O(n log n)

• max-heap - Szótár.net (en-hu)
• max-heap - Sztaki (en-hu)
• max-heap - Merriam–Webster
• max-heap - Cambridge
• max-heap - WordNet
• max-heap - Яндекс (en-ru)
• max-heap - Google (en-hu)
• max-heap - Wikidata
• max-heap - Wikipédia (angol)