binomial heap (tsz. binomial heaps)
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.
Egy binomiális fa B_k:
kB_k egy B_{k-1} gyökérbe csatolt példányaB_k úgy épül fel, hogy egy B_{k-1}-et a gyökér bal legidősebb gyermekéhez csatolunk
B_0: 1
B_1: 1
|
2
B_2: 1
/ \
2 3
|
4
B_k típusú fából legfeljebb egy darab lehet → binárisan tárolható
| 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
|
H1 és H2 is tartalmaz B_2-t, egyesítjük → új B_3B_k lehet → bináris logika szerint működik
| 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 |
| 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ő.
| 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 |
Ha 13 elem van, akkor a binomiális erdőben ezek a fák szerepelnek:
13 = 1101₂ → B₀, B₂, B₃