max-heap

Üdvözlöm, Ön a max-heap szó jelentését keresi. A DICTIOUS-ban nem csak a max-heap szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a max-heap szót egyes és többes számban mondani. Minden, amit a max-heap szóról tudni kell, itt található. A max-heap szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Amax-heap és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Főnév

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.



📐 Szerkezet

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.



🧠 Indexképletek

Egy heap pozícióhoz:

Kapcsolat Index képlete
Szülő (i - 1) / 2
Bal gyerek 2 * i + 1
Jobb gyerek 2 * i + 2



🛠️ Alapműveletek

Művelet Leírás Időkomplexitás
insert(x) Új elem beszúrása O(log n)
getMax() Maximum lekérdezése (gyökér) O(1)
extractMax() Maximum eltávolítása, és újrendezés O(log n)
heapify() Max-heap visszaállítása a szabály szerint O(log n)
buildHeap() N darab elem kupaccá alakítása O(n)



📊 Példa

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

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

Tömbként tárolva:



🔄 insert(x) működése

  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”.



🔄 extractMax()

  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”.



🧪 Egyszerű C++ implementáció

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;
    }
};

🎯 Alkalmazások

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



📈 Heapsort röviden

  • É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)



✅ Összefoglalás

Tulajdonság Érték
Legnagyobb elem Gyökér (O(1))
Beszúrás ideje O(log n)
Törlés ideje O(log n)
Tárolási mód Tömb (array)
Sorrend Nem teljes rendezés, csak részleges