max-heap

Angol

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[i] 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:

[100, 50, 30, 20, 10, 5, 1]

---

🔄 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[l] > heap[largest]) largest = l;
        if (r < n && heap[r] > heap[largest]) largest = r;

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

    void heapifyUp(int i) {
        while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
            swap(heap[i], heap[(i - 1) / 2]);
            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[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return maxVal;
    }

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

---

🎯 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

---

További információk

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