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ójaA kupac egy olyan bináris fa, amely
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űveletekA kupac adatszerkezetnek a következő műveleteket kell megvalósítania:
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ásA 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ásaT[ ] tömb lefoglalása N := 0 Emelés és süllyesztésA 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ésAmí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 |
Programozás >