Kupac (adatszerkezet)
| Kupac | |
| Típus | Fa |
A kupac (más néven halom, angolul heap) egy speciális fa alapú adatszerkezet, amely eleget tesz a kupac tulajdonságnak, azaz ha a B csúcs fia az A csúcsnak, akkor kulcs(A) ≥ kulcs(B) - és ebben az esetben a kupacot max-kupacnak (vagy maximum-kupacnak) nevezzük. Az összehasonlítás megfordításával min-kupacot (azaz minimum-kupacot) kapunk, melyben minden A csúcsból leszármazó B csúcshoz kulcs(B) ≥ kulcs(A). A kupac egy maximálisan hatékony implementációja a prioritási sor adatszerkezetnek.
Alkalmazása
A kupac adatszerkezet különböző fajtáit több algoritmus hatékony implementációja során alkalmazhatjuk:
- Tömbök kupacos rendezése során, mivel a bináris kupacok tömb formájában is felírhatóak.
- Kiválasztó algoritmusokban a k-adik legkisebb vagy legnagyobb elem megkeresése lineáris időben elvégezhető kupaccal.
- Súlyozott gráfokat bejáró algoritmusok gyorsíthatóak kupacok alkalmazásával (pl. Dijkstra-algoritmus)
Műveletek kupacokban
| Művelet | Bináris | Binomiális | Fibonacci |
|---|---|---|---|
| létrehoz | Θ(1) | Θ(1) | Θ(1) |
| maxkeres | Θ(1) | O(log n) | Θ(1) |
| maxtöröl | Θ(log n) | Θ(log n) | O(log n) |
| növel | Θ(log n) | Θ(log n) | Θ(1) |
| beszúr | Θ(log n) | O(log n) | Θ(1) |
| összefűz | Θ(n) | O(log n) | Θ(1) |
A max-kupacokon értelmezett alapműveletek:
- Létrehoz: Egy üres kupac létrehozása.
- Maxkeres: A kupac maximális kulcsát adja vissza.
- Maxtöröl: A kupac gyökerét (maximális kulcsát) törli.
- Növel: Egy kulcs növelése.
- Beszúr: Egy újabb kulcs beszúrása.
- Összefűz: Két kupacot összefűz, mindkettő elemeit megtartva.
A min-kupacokon hasonló műveleteket értelmezünk; a maximumkeresés és -törlés helyett minimumkeresést és törlést, illetve a kulcsnövelés helyett kulcs-csökkentést.
A főbb kupactípusokban az egyes műveletek komplexitása max-kupac esetén (min-kupacban a megfelelő művelet komplexitása megegyezik) a jobb oldali táblázatban látható. A táblázatban O(f) esetén a lépésszám felülről becsülhető f konstansszorosával (lásd O jelölés), θ(f) esetén pedig a lépésszám pontosan f konstansszorosa.
Típusai
- 2-3 kupac
- Bináris kupac
- Binomiális kupac
- Fibonacci-kupac
- Intervallumkupac
- Párosító kupac
Források
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Új algoritmusok. Scolar Kiadó, 126–140. o.. ISBN 978 963 9193 90 1
Informatikai portál • összefoglaló, színes tartalomajánló lap
 | Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
