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

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

• 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