„Kupac (adatszerkezet)” változatai közötti eltérés
[ellenőrzött változat] | [ellenőrzött változat] |
a Informatikai portál AWB |
Halomnak is hívják |
||
3. sor: | 3. sor: | ||
|típus=Fa (adatszerkezet){{!}}Fa |
|típus=Fa (adatszerkezet){{!}}Fa |
||
}} |
}} |
||
A '''kupac''' egy speciális [[fa (gráfelmélet)|fa]] alapú [[adatszerkezet]], amely eleget tesz a ''kupac tulajdonságnak'', azaz ha a '''B''' [[csúcs (gráfelmélet)|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. |
A '''kupac''' (más néven '''halom''') egy speciális [[fa (gráfelmélet)|fa]] alapú [[adatszerkezet]], amely eleget tesz a ''kupac tulajdonságnak'', azaz ha a '''B''' [[csúcs (gráfelmélet)|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 == |
== Alkalmazása == |
A lap 2014. december 31., 11:01-kori változata
Kupac | |
Típus | Fa |
A kupac (más néven halom) 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
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