Kupacrendezés

Kupacrendezés
A kupacrendezésre egy példa
Kategória	Rendezési algoritmus
Legrosszabb időbonyolultság	$O(n\log n)$
Legjobb időbonyolultság	$\Omega (n),O(n\log n)$
Átlagos idő bonyolultság	$O(n\log n)$
Legrosszabb tár bonyolultság	$O(1)$ kiegészítés
Optimális	soha

A kupacrendezés összehasonlító rendezési algoritmus, és a kiválasztó rendezések családjába tartozik. Helyben rendező, nem stabil rendezés.

A kupacrendezés a használt adatszerkezetről kapta a nevét, a kupacról. A kupacrendezés működése során előbb felépíti a kupacot, majd egyesével kiemeli a gyökérelemet, ami a kupac definíciója miatt a legnagyobb/legkisebb elem lesz.

Áttekintés

A kupacrendezés nevének megfelelően egy kupac felépítésével kezdődik. Az adatok felhasználásával létrehozunk egy kupacot, majd eltávolítjuk a legnagyobb elemet. A gyökérelem törlésével elromlott a kupac tulajdonság, ezt helyre kell állítanunk. Az elem törlése lehetséges úgy is, hogy a kupac legalsó szintjének jobb szélső elemével cserélünk, és az új jobb szélső elemet nem tekintjük a kupac részének. A helyreállítás úgy lehetséges, hogy az eredeti jobb szélső elemet a gyökérbe helyezzük, majd süllyesztjük. Az utóbbi változatban ez megegyezik a gyökérelem süllyesztésével. A süllyesztés a szülő elemet mindig a nagyobbik, illetve a jobb oldali gyerekkel cseréli, ha van ilyen, és nagyobb a szülőnél. Az algoritmus ezután mindig eltávolítja a következő legnagyobb, azaz a gyökérben található elemet, és helyreállítja a kupac tulajdonságot. Ha a kupacrendezés helyesen, tömbbel kerül implementálásra, és a jobb szélső elemmel való törlést választjuk, a tömb rendezett lesz, és nincs szükség az eredeti tömbnél több memóriára.

A kupac tulajdonság feltételezi, hogy minden szülő elem nagyobb, vagy azonos értékű, mint gyerekei. Ennek megfordításával minimális gyökerű kupacot kapunk, és csökkenően rendezett tömböt készíthetünk a fenti algoritmussal.

Összehasonlítás más rendezésekkel

A kupacrendezés a gyorsrendezéshez hasonló hatékonysággal rendelkezik. A gyorsrendezés általában valamivel gyorsabb, viszont legrosszabb esetben futásideje elérheti a Θ(n²) nagyságrendet. Bizonyos adatmennyiség felett a négyzetes futásidő elfogadhatatlan, a gyorsrendezés implementációjának ismeretében pedig könnyen elérhető, ezzel csökkentve az algoritmus biztonságát. Mivel a kupacrendezés nagyságrendje Θ(n log n) marad, jellemzően ezt az algoritmust választják a gyorsrendezéssel szemben azokban a rendszerekben, ahol a biztonság meghatározó tényező.

A kupacrendezés szembeállítható az összefésülő rendezéssel is. Időigényük hasonló, memóriaigényben az összefésülő rendezés rosszabbul állhat. Az összefésülő rendezés rendelkezik néhány előnnyel a kupacrendezéshez képest:

• Az összefésülő rendezés stabil rendezés.
• Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható.

Forrás

Ez a szócikk részben vagy egészben a Heapsort című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Kiegészítő irodalom

• Binary and Binomial Heaps. Princeton University (2002) 

• Informatikai algoritmusok. Szakmai segédanyag programtervező matematikusok részére, mobiDIÁK könyvtár. Debreceni Egyetem Informatikai Kar: mobiDIÁK könyvtár (2006) 

• Ronald L. Rivest, Charles E. Leiserson; Thomas H. Cormen. Algoritmusok. Műszaki Könyvkiadó Kft. (2001). ISBN 9789631630299 

• Thomas H. Cormen, Charles E. Leiserson - Ronald L. Rivest - Clifford Stein. Új algoritmusok. Scolar Kiadó (2003). ISBN 9789639193901 

• Rónyai-Ivanyos-Szabó: Algoritmusok, Typotex, 1998
• Gács-Lovász: Algoritmusok, Tankönyvkiadó, 1989
• Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise, Műszaki Kiadó, 1982