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 bélyegkép|200px|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
Kategória:Adatszerkezetek