Kupac (adatszerkezet)

A Wikipédiából, a szabad enciklopédiából



Kupac
Típus Fa

A kupac 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[szerkesztés | forrásszöveg szerkesztése]

Egy bináris maximum-kupac

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Új algoritmusok. Scolar Kiadó, 126–140. o. ISBN 978 963 9193 90 1