Mound - online rejtvények
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
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.
