Kupacrendezés

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.

A kupac létrehozásához a rendezés érdekében sorvektorban vesszük fel az elemeket, az indexek 0-tól -ig terjed. Az ábrázolás érdekében bármely, rendszámú elemnek a gyermekei a rendszámú elemek. Ekkor a legutolsó elem, aminek gyermeke lehet, az rendszámú elem. Innentől egyesével lépegetünk vissza.

Minden szülő esetén összehasonlítjuk őt a gyermekeivel, és ha valamelyiknél kisebb, akkor vele felcseréljük. Ennek révén a vektorban rendezett láncok keletkeznek, és így a legfelső (0 rendszámú) elem biztosan a vektor maximális elem lesz. Ezt töröljük (kiemeljük).

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.

Példarendezés Vegyünk egy rendezetlen tömböt! Az egyszerűség kedvéért legyen ez egy magyar szó, aminek betűit ábécé-rendbe akarjuk állítani: K I S M A L A C 0 1 2 3 4 5 6 7 A betűk alatt a rendszámuk van, az azonosíthatóság kedvéért. Itt , így a legalsó szülő elem az rendszámú M. Az ő egyetlen gyermeke a rendszámú C. Mivel az ábécében M>C, a rend megmarad.

A következő elem az S, aminek gyermekei L és A. Megint S a maximális elem, ezért marad a helyén. Következik az I, aminek gyermekei M és A. Mivel M nagyobb, ezért cserélünk: K M S I A L A C 0 1 2 3 4 5 6 7 Most jön a 0-s rendszámú K. A gyermekei M és S, közülük az S a legnagyobb, és ez nagyobb, mint K, ezért cserélünk: S M K I A L A C 0 1 2 3 4 5 6 7

Kész az első bináris fa. Az első elemet a vektor végére illesztjük, és a hosszt csökkentjük eggyel: és M K I A L A C S 0 1 2 3 4 5 6 Az utolsó elemet nem indexeljük, őt már nem kell rendezni. Következő kör.

A legalsó szülő a 2 indexű I, a gyermekei az A és C. Ezeknél nagyobb, úgyhogy nincs csere. Következő szülő az 1 indexű K, gyermekei A és L, ezért cserélünk L-lel: M L I A K A C S 0 1 2 3 4 5 6

Az M a legfelső szülő, ő nagyobb a gyermekeinél, L-nél és I-nél. Megint leszállítjuk a legfelső elemet, a sort léptetjük, a maximális indexet csökkentjük: K I A L A C S M 0 1 2 3 4 5

A 2-es rendszámú A a legalsó szülő, egyetlen gyermeke C, ami nagyobb nála, így cserélünk: K I C L A A S M 0 1 2 3 4 5

I gyermekei L és A, megint cserélünk: K L C I A A S M 0 1 2 3 4 5 K gyermekei L és C, megint van csere: L K C I A A S M 0 1 2 3 4 5 L leszáll, léptetés, csökkentés: K C I A A S M L 0 1 2 3 4

C gyermekei A és A, így nincs csere. K gyermekei C és I, itt sincs csere. Léptetünk, csökkentünk: C I A A S M L K 0 1 2 3

I gyermekei A és A, szóval nicns csere. C gyermekei I és A, itt cserélünk: I C A A S M L K 0 1 2 3 Léptetünk, csökkentünk: C A A S M L K I 0 1 2

C gyermekei A és A, nincs csere. Léptetés, csökkentés: A A S M L K I C 0 1 Mivel A = A, őket egymás után beírjuk a vektor végére, és kész a rendezett, csökkenő sorozat: S M L K I C A A

Így, leírva hosszadalmas és lehetetlenül bonyodalmas az ember számára, azonban ha a lépéseket összeszámláljuk, meglepő következtetésre juthatunk: 21 lépésben végzünk.

A hagyományos, összehasonlításos rendezés esetén a lépésszám nagyjából 170, azaz a kupacrendezés ez esetben kilencszer gyorsabb volt. Ami az ember számára a bonyodalmat jelentette, az a szülő-gyermek kapcsolat, amit a számítógép a cserékkel és léptetéssel azonos nagyságrendú sebességgel végzi el.

Ö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 az 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 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éses 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ó.

Jegyzetek

Fordítás

Kiegészítő irodalom

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

Kapcsolódó szócikkek Rendezés (programozás) Koktélrendezés Fésűs rendezés Gyorsrendezés Beszúrásos rendezés

Kategória:Rendezési algoritmusok

no:Sorteringsalgoritme#Heap sort