binary heap

Angol

Főnév

binary heap (tsz. binary heaps)

1. (informatika) bináris kupac

---

A binary heap (bináris kupac) egy olyan teljes bináris fa, amely kielégíti a heap-tulajdonságot, vagyis minden szülő-gyerek kapcsolatnál az alábbiak igazak:

• Min-heap: a szülő kisebb vagy egyenlő, mint a gyermekei → könnyen lekérhető minimum
• Max-heap: a szülő nagyobb vagy egyenlő, mint a gyermekei → könnyen lekérhető maximum

A binary heap gyakori alapja a prioritási soroknak (priority queues), illetve a Heapsort algoritmusnak.

---

📦 Jellemzők

• Teljes bináris fa: minden szint balról jobbra teljesen kitöltött (kivéve az utolsó szintet)
• Tömb (array) alapú reprezentáció:
  • Gyökér: heap[0]
  • Bal gyerek: heap[2i + 1]
  • Jobb gyerek: heap[2i + 2]
  • Szülő: heap[(i - 1) / 2]

---

🛠️ Alapműveletek és komplexitás

Művelet	Leírás	Időkomplexitás
insert(x)	Új elem hozzáadása	O(log n)
getMin() / getMax()	Gyökér visszaadása	O(1)
extractMin() / extractMax()	Gyökér eltávolítása és újrarendezés	O(log n)
heapify()	Egész fa újrarendezése	O(log n)
buildHeap()	Lista átalakítása kupaccá	O(n)

---

📊 Példa (Min-heap)

        5
      /   \
    10     8
   /  \   /
 15  12  11

Tömbként tárolva:

[5, 10, 8, 15, 12, 11]

Minden szülő kisebb a gyerekeinél → min-heap.

---

🔄 Működés

insert(x)

1. Beszúrjuk x-et a tömb végére.
2. Fölfele “bubble-up”: összehasonlítjuk a szülőjével, és szükség szerint cserélünk.

extractMin() (min-heap)

1. Kivesszük a heap[0] elemet.
2. Helyére betesszük az utolsó elemet.
3. Lefele “heapify-down”: a gyerekekkel cserélgetjük, amíg a heap-tulajdonság helyre nem áll.

---

🔄 heapify(i) (top-down)

void heapify(vector<int>& heap, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < heap.size() && heap[l] < heap[smallest]) smallest = l;
    if (r < heap.size() && heap[r] < heap[smallest]) smallest = r;

    if (smallest != i) {
        swap(heap[i], heap[smallest]);
        heapify(heap, smallest);
    }
}

---

🔃 buildHeap() (bottom-up)

void buildHeap(vector<int>& heap) {
    for (int i = heap.size() / 2 - 1; i >= 0; --i) {
        heapify(heap, i);
    }
}

Ez O(n) időben alakít át egy rendezetlen tömböt egy min-heap struktúrává.

---

💡 Alkalmazások

• Prioritási sor (priority queue)
• Heapsort
• Dijkstra algoritmus (bináris vagy Fibonacci heap-pel)
• Event scheduling szimulációkban
• Median kiszámítása 2 kupaccal (min + max)

---

🔍 Bináris vs. egyéb heap-ek

Adatszerkezet	Insert	Extract Min	Decrease Key	Merge
Binary heap	O(log n)	O(log n)	O(log n)	O(n)
Binomiális heap	O(log n)	O(log n)	O(log n)	O(log n)
Fibonacci heap	O(1)	O(log n)*	O(1)	O(1)

---

🧪 C++ osztályváz (Min-heap)

class BinaryHeap {
    vector<int> heap;

    void heapifyDown(int i);
    void heapifyUp(int i);

public:
    void insert(int val);
    int getMin();
    int extractMin();
};

---

✅ Összefoglalás

A binary heap egy hatékony, tömbben tárolt prioritási sor, amely lehetővé teszi a minimum vagy maximum gyors elérését és módosítását. Használata egyszerűbb, mint a haladóbb struktúráké (pl. Fibonacci heap), és a legtöbb gyakorlati célra tökéletesen megfelel.

További információk

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