„Kupac (adatszerkezet)” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
EmausBot (vitalap | szerkesztései)
a r2.7.2+) (Bot: következő módosítása: et:Kuhi
a Fa (adatszerkezet)
1. sor: 1. sor:
{{Adatszerkezet infobox
{{Adatszerkezet infobox
|név=Kupac
|név=Kupac
|típus=Fa
|típus=Fa (adatszerkezet)
}}
}}
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''' 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 lap 2012. szeptember 24., 16:42-kori változata

Kupac
TípusFa (adatszerkezet)

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

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

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