binomial heap

Angol

Főnév

binomial heap (tsz. binomial heaps)

1. (informatika) A binomiális kupac (angolul: binomial heap) egy haladó prioritási sor megvalósítás, amelyet úgy terveztek, hogy gyorsan támogatja a heap-ek összeolvasztását (merge). Hatékony alternatívája a bináris heapnek, különösen akkor, ha gyakori a két prioritási sor egyesítése.

---

🧠 Alapgondolat

A binomiális kupac egy binomiális fákból álló erdő (forest), amely:

* Minden egyes fa egy binomiális fa,

• A fa szerkezete binomiális együtthatókra épül,
• Egy binomiális kupac maximum log n binomiális fát tartalmaz, és minden fokozatból legfeljebb egyet.

---

🌲 Mi az a binomiális fa?

Egy binomiális fa B_k:

• Fokszáma: k
• Tartalmaz 2^k csomópontot
• Rekurzív szerkezet: B_k egy B_{k-1} gyökérbe csatolt példánya
• Minden B_k úgy épül fel, hogy egy B_{k-1}-et a gyökér bal legidősebb gyermekéhez csatolunk

Példa:

B_0:   1

B_1:   1
       |
       2

B_2:   1
      / \
     2   3
    |
    4

---

🔧 Binomiális kupac jellemzői

• Több binomiális fát tartalmaz
• Minden fa max- vagy min-heap tulajdonságú
• Minden B_k típusú fából legfeljebb egy darab lehet → binárisan tárolható

---

🛠️ Műveletek és időkomplexitás

Művelet	Idő (amortizált)	Leírás
insert(x)	O(log n)	Új elem hozzáadása új B_0 fa formájában
getMin()	O(log n)	Végig kell nézni a gyökereket
extractMin()	O(log n)	Legkisebb gyökér törlése, gyerekei új kupaccá formálása
merge(H1, H2)	O(log n)	Két binomiális kupac egyesítése bináris összeadásként
decreaseKey()	O(log n)	Csomópont kulcsának csökkentése, felfelé mozgatás
delete()	O(log n)	Kulcs csökkentése -∞-re, majd extractMin

---

🔄 Merge működése – bináris analógia

• Olyan, mintha bináris számokat adnál össze:
  • Ha H1 és H2 is tartalmaz B_2-t, egyesítjük → új B_3
  • Mindig legfeljebb egy B_k lehet → bináris logika szerint működik

---

📦 Alkalmazások

Terület	Példa
Prioritási sorok	Több kis heap gyors összeolvasása
Ütemezés	Min heap vagy max heap alapú
Graf algoritmusok	Alternatíva Fibonacci heap helyett
Funkcionális nyelvek	Reprezentálható mint persistent struktúra

---

🧾 Összehasonlítás

Adatszerkezet	Insert	ExtractMin	Merge	DecreaseKey
Bináris heap	O(log n)	O(log n)	O(n)	O(log 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)*

\* Amortizált idő.

---

✅ Összefoglalás

Tulajdonság	Binomiális kupac
Struktúra	Binomiális fák erdeje
Műveletek	Hatékony, főleg merge()
Tárolás	Bináris logika szerint rendezve
Legnagyobb előny	Két prioritási sor gyors összeolvasztása
Legnagyobb hátrány	Bonyolultabb, mint bináris heap

---

📚 Extra: Binomiális kupac bináris ábrázolása

Ha 13 elem van, akkor a binomiális erdőben ezek a fák szerepelnek:

13 = 1101₂ → B₀, B₂, B₃

További információk

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