Programozás‎ > ‎

Kupac

A kupac adatszerkezet - többek között - rendezésre, illetve prioritási sorok megvalósítására használható. Ereje, hogy időben dinamikusan változó adatszerkezetben hatékonyan tudja megadni az aktuális legnagyobb (vagy legkisebb) elemet.

A kupac definíciója

A kupac egy olyan bináris fa, amely 
  • majdnem teljesen kiegyensúlyozott, vagyis a legalsó szint kivételével minden csomópontnak van bal és jobb gyermeke, vagy nincs se bal se jobb gyermeke; 
  • bármely csomópontban lévő elem kulcsa nagyobb (kisebb) a csomópont gyermekeiben tárolt elemek kulcsánál.
A  fentiekből következik, hogy a kupac tetején (a bináris fa gyökerében) lévő elem maximális (minimális), és ez a tulajdonság rekurzívan igaz bármely rész-kupacra (a fa egy csomópontjából induló részfára).

A következő ábrán egy maximum-kupac látható, tehát egy olyan kupac, amelyben bármely elem kulcsa nagyobb vagy egyenlő, mint gyermekeinek kulcsa.


Kupac műveletek

A kupac adatszerkezetnek a következő műveleteket kell megvalósítania:
  • üres kupac létrehozása
  • adott kulcsú elem beszúrása a kupacba
  • maximális/minimális kulcsú elem kiolvasása
  • maximális/minimális kulcsú elem kiolvasása és törlése a kupacból
  • adott elem kulcsának módosítása (növelés vagy csökkentés), majd a kupactulajdonság helyreállítása
  • (két kupac összeolvasztása)

Kupac reprezentáció

Az egyik szokásos megvalósításban a kupac elemeit egy tömbben tároljuk. Kupacok esetében gyakran 1-től indexeljük a tömböt, annak ellenére, hogy C-ben vagy Java-ban a 0 a szokásos kezdőindex. A kupac teteje (a fa gyökere) az 1-es indexű elem, továbbá az i indexű elem gyerekeinek indexe 2*i illetve 2*i+1.



Megvalósítás

A továbbiakban egy maximum-kupac műveleteit adjuk meg, ebből egyszerű átalakítással a minimum-kupac is elkészíthető. A kupac elemeit egyszerű egész számokként kezeljük az algoritmusban, hogy a kód áttekinthetőbb legyen. A valódi implementációkban az elemek összetett objektumok is lehetnek, amelyek valamilyen kulcs szerint rendezhetők.

Az adatok a T[ ] tömbben lesznek, az aktuális elemszám N. Ha tudunk (értelmes) felső becslést adni a kupac maximális méretére, akkor felvehetjük a tömböt ekkorára. Ha nincs ilyen becslés, vagy értelmetlenül nagy lenne a lefoglalt memória mérete, akkor érdemes dinamikusan átméretezhető tömbökkel dolgozni. A továbbiakban az átméretezéssel nem foglalkozunk, feltesszük, hogy van elég memória és a tömb elég nagy ahhoz, hogy a szükséges kupac-műveletek elvégezhetők legyenek.

Üres kupac létrehozása

T[ ] tömb lefoglalása
N := 0

Emelés és süllyesztés

A kupacműveletek során - átmenetileg - előfordulhat, hogy egy elem megsérti a kupactulajdonságot, vagyis nagyobb a szülőjénél, vagy nála nagyobb valamelyik gyereke. Ilyenkor az emelés illetve a süllyesztés művelettel lehet helyére mozgatni az elemet, hogy helyreálljon a kupactulajdonság. Ezek a műveletek ismerik a mozgatandó elem tömbbeli indexét.

Emelés

Amíg az aktuális elem kulcsa nagyobb, mint a szülőé, addig felfelé mozgatjuk a kupacban úgy, hogy felcseréljük a szülő elemmel. Ha az index i, akkor a szülő indexe i / 2, ahol egész osztás értendő.

emel(i):

    Ciklus amíg i > 1 és T[i / 2] < T[i]
        Csere(i / 2, i)
        i := i / 2
    Ciklus vége




Süllyesztés

Amíg a vizsgált elem kisebb valamelyik gyerekénél, addig lefele mozgatjuk a kupacban úgy, hogy felcseréljük a nagyobbik gyerekével. Ha az aktuális index i, akkor a gyerekek indexe 2 * i és 2 * i + 1, de vigyázni kell, mert a kupac alján előfordulhat, hogy csak bal oldali gyerek van, jobb oldali már nem.

süllyeszt(i):

    Ciklus amíg 2 * i <= N
        j = 2 * i
        Ha j < N  és  T[j] < T[j+1] akkor 
            j := j+1
        Elágazás vége
        Ha T[j] <= T[i] akkor kilépés a ciklusból
        Csere(i, j)
        i := j
    Ciklus vége






Ugyanez picit hatékonyabban (a cserék helyett csak felfelé másolunk, és végén írjuk vissza a süllyesztett elemet):


süllyeszt(i): 

    E := T[i]
    apa := i
    fiu := 2*apa
    Ha fiu < N és T[fiu+1]>T[fiu] akkor
        fiu++
    Elágazás vége

    Ciklus amíg fiu <= N és T[fiu] > E
        T[apa] := T[fiu]
        apa := fiu
        fiu := 2*apa
        Ha fiu < N és T[fiu+1]>T[fiu] akkor
            fiu++
        Elágazás vége
    Ciklus vége
    T[apa] := E

Beszúrás

Beírjuk a tömb végére az új elemet, majd az emelés művelettel betesszük az igazi helyére.

beszúr(kulcs):
    
    N := N + 1
    T[N] := kulcs
    emel(N)


Maximum kiolvasása és törlése

A maximumot T[1]-ben találjuk. Törléséhez felcseréljük a tömb utolsó elemével, majd az új T[1]-et (eggyel kisebb N mellett) a helyére süllyesztjük.

x := törölmax():

    x := T[1]
    Csere(1, N)
    N := N - 1
    süllyeszt(1)

Hatékonyság


Alkalmazások

Kupacrendezés

A rendezendő tömbben építjük fel a kupacot, majd mindig kivesszük a maximális elemet, és a tömb végére cseréljük. Az eggyel kisebb kupaccal folytatjuk. Részletek itt.

Prioritási sor

A kupac tetejéről kivehető a maximális / minimális elem, majd helyreállítható a kupacrendezés. Az emelés és a süllyeszt eljárásokkal az is megvalósítható, hogy egy kulcs csökkentése vagy növelése után megtaláljuk az elem új helyé a kupacban.

Dijkstra-algoritmus: legrövidebb út élsúlyozott gráfban

A kupacban tároljuk, hogy az irányított élsúlyozott gráf csúcsaihoz pillanatnyilag milyen hosszú utat ismerünk. (Itt szükség van egy "végtelen" értékre is.) Mindig a minimális becslésű csúcsot véglegesítjük, vagyis a törölmin eljárást használjuk. A véglegesített csúcs szomszédainak csökkenhet a becslése, ezért ezekre az emel eljárást kell meghívni, hogy helyükre kerüljenek a kupacban.