Egyesítés kupac
Az összevonható kupac egy olyan adatstruktúra , amely a következő öt műveletet támogatja :
- Üres kupac létrehozása ( eng. Make heap );
- Csomópont beszúrása kupacba ( angol Insert );
- Keressen egy csomópontot a kupacban , amelyik rendelkezik a minimális kulccsal ( angol Minimum );
- Minimális kulcsú csomópont eltávolítása a kupacból ( eng. Extract minimum );
- Egy új kupac létrehozása, amely tartalmazza a kupacok összes csomópontját és ( eng. Union ).
Megvalósítások
A következő két adatstruktúra egyesített kupac megvalósítás:
Ezek az adatstruktúrák két további műveletet is támogatnak:
- Új kulcsérték ( Decrease key ) hozzárendelése egy csomóponthoz a kupacban (feltételezzük, hogy az új kulcsérték nem haladja meg az aktuálisat);
- Csomópont eltávolítása a kupacból ( eng. Delete ).
| Művelet | binomiális kupac | fibonacci kupac |
|---|---|---|
| rakj kupacot | Θ(1) | Θ(1) |
| Beszúrás | O ( lgn ) | Θ(1) |
| Minimális | O ( lgn ) | Θ(1) |
| Kivonat minimum | Θ(lg n ) | O ( lgn ) |
| Unió | Ω(lg n ) | Θ(1) |
| Csökkentő gomb | Θ(lg n ) | Θ(1) |
| Töröl | Θ(lg n ) | O ( lgn ) |
Megjegyzés: Binomiális kupac esetén a legrosszabb eset, Fibonacci kupac esetén amortizált idő.
Megjegyzés. Alapértelmezés szerint az egyesített kupacok nem csökkenő összevonható kupacok ( Mergeable min-heap ). Vannak nem növekvő összevonható kupacok is ( Mergeable max-heap ), amelyek a következő műveleteket támogatják:
- Üres kupac létrehozása ( eng. Make heap );
- Csomópont beszúrása kupacba ( angol Insert );
- Keressen egy csomópontot a kupacban , amely a maximális kulcsot tartalmazza ( eng. Maximum );
- Maximum kulccsal rendelkező csomópont eltávolítása a kupacból ( Maximum kivonása );
- Egy új kupac létrehozása, amely tartalmazza a kupacok összes csomópontját és ( eng. Union ).
- Új kulcsérték hozzárendelése egy csomóponthoz a kupacban ( Inrease key );
- Csomópont eltávolítása a kupacból ( eng. Delete ).
Irodalom
- Thomas H. Kormen et al. Algoritmusok: szerkesztés és elemzés. - 2. kiadás - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .