Heapify All The Things With Heap Sort

Vaidehi Joshi

Follow

Júl 13, 2017 – 11 min read

Egyszer valaki azt mondta nekem, hogy az informatikában minden fontos dolog a fákra fut ki. Szó szerint csak fákra. Ezek segítségével tudunk dolgokat építeni, elemezni és értelmezni (igen, lehet, hogy itt némi előjelzés történik, ne aggódj, ha még nem érted, mert hamarosan érthető lesz!) És még arra is használhatjuk őket, hogy – kitaláltad! – rendezni a dolgokat.

Ah, rendezés. Annyi mindent csináltunk belőle az elmúlt hetekben, de most már a rendezési kalandozásunk végéhez közeledünk. Azonban lehetetlen és igazságtalan úgy beszélni a rendezésről, hogy ne beszélnénk a rendezés egy speciális fajtájáról, amely a legújabb adatszerkezetet használja az adatszerkezeti eszköztárunkban.

Nemrég tanultuk meg szeretni a heapeket, a bináris fák egy speciális fajtáját, amely szigorú szabályokat követ, és olyan dolgok megvalósítására használják, mint a prioritási sorok és a háttérmunkák. De nem ezek az egyetlen dolgok, amikre a heapek jók. Kiderült, hogy a bináris halmokat gyakran nem másra használják, mint hatékony rendezésre. Sok program támaszkodik a halmazrendezésre, mivel történetesen ez az egyik leghatékonyabb módja egy tömb rendezésének. És most, hogy már tudjuk, mi az a halom, megpróbálhatjuk megérteni, miért működik olyan jól, amikor a rendezés problémájáról van szó!

Mielőtt belevetnénk magunkat a halomrendezésbe, győződjünk meg róla, hogy a halmok rendben vannak a fejünkben. Emlékezhetünk arra, hogy a halom valójában nem más, mint egy bináris fa néhány további szabállyal, amelyet követnie kell: először is, mindig halomszerkezetűnek kell lennie, ahol a bináris fa minden szintje balról jobbra haladva van feltöltve, másodszor pedig vagy max halomként, vagy min halomként kell rendezni. A halomrendezés szempontjából kizárólag max halmokkal fogunk foglalkozni, ahol minden szülő csomópont (beleértve a gyökeret is) nagyobb vagy egyenlő, mint a gyermek csomópontjainak értéke.

Oké, térjünk rá az óra kérdésére: hogyan rendezünk halmok segítségével? Nos, ahhoz, hogy megválaszolhassuk ezt a kérdést, először is meg kell értenünk, mi is az a halmazrendező algoritmus!

A halmazrendező algoritmus olyan rendezési technika, amely bináris halmaz adatszerkezetekre támaszkodik. Mivel tudjuk, hogy a halmoknak mindig egy meghatározott sorrendet kell követniük, kihasználhatjuk ezt a tulajdonságot, és felhasználhatjuk a legnagyobb, maximális értékű elem megtalálására, valamint az elemek szekvenciális rendezésére úgy, hogy kiválasztjuk a halom gyökércsomópontját, és hozzáadjuk a tömb végéhez.

Azt már tudjuk, hogy a halomrendezés hatékony módja egy rendezetlen tömb rendezésének; de mi köze van egy tömbnek a halomhoz? És hogyan rendezünk egy tömböt egy halom segítségével? Nos, három kulcsfontosságú lépés van ahhoz, hogy ez a gyakorlatban hogyan is működik. Ezeket mindjárt részletesebben is megnézzük, de először is vessünk egy magas szintű pillantást arra, hogy mi ez a három lépés.

1. Kezdésnek van egy rendezetlen tömbünk. Az első lépés az, hogy fogjuk ezt a tömböt, és halommá alakítjuk; esetünkben max halommá akarjuk alakítani. Tehát át kell alakítanunk és egy max halmazt kell építenünk a rendezetlen tömb adatainkból. Általában ezt egyetlen függvény foglalja magába, amelynek neve lehet valami olyasmi, mint buildMaxHeap.
2. Mihelyt a tömb adataink max heap formátumban vannak, biztosak lehetünk benne, hogy a legnagyobb érték a heap gyökércsomópontjában van. Ne feledjük, hogy bár a teljes halom nem lesz rendezett, ha helyesen és hibátlanul építettük fel a max heapünket, akkor a halom minden egyes szülő csomópontja nagyobb értékű lesz, mint a gyermekei. Tehát a legnagyobb értéket – amely a gyökércsomópontban található – a halom végére fogjuk áthelyezni azáltal, hogy kicseréljük az utolsó elemmel.
3. Most a halom legnagyobb eleme az utolsó csomópontban található, ami nagyszerű. Tudjuk, hogy a rendezett pozíciójában van, így teljesen eltávolítható a halomból. De van még egy lépés: meg kell győződnünk arról, hogy az új gyökércsomópont elem a megfelelő helyen van! Nagyon valószínűtlen, hogy a gyökércsomópont pozíciójába cserélt elem a megfelelő helyen van, ezért a gyökércsomópont elemet lefelé mozgatjuk a megfelelő helyre, egy függvény segítségével, amelynek általában valami olyasmi a neve, mint heapify.

És lényegében ennyi! Az algoritmus addig ismétli ezeket a lépéseket, amíg a halom le nem csökken egyetlen csomópontra. Ekkor már tudja, hogy a rendezetlen tömb minden eleme a rendezett pozícióban van, és hogy az utolsó megmaradt csomópont lesz végül a rendezett tömb első eleme.

Oké, tudom, hogy azt mondtam, hogy ez a kupacrendezésnek csak három lépése van. De ha ez a három lépés zavarosnak tűnik, ne aggódj; elég bonyolult és nehezen érthető lehet, amíg nem látod őket működés közben. Valójában úgy gondolom, hogy ennek az algoritmusnak sokkal több értelme van egy illusztrált példával. Mivel a halmazok egyfajta fák, segít vizualizálni őket, ugyanúgy, ahogyan a bináris fák esetében is tesszük. Úgyhogy tegyük is ezt most!

Nézett már a halomrendezés motorháztetője alá?

Eljött az idő a halomrendezés tanításának abszolút kedvenc részéhez: a rajzoláshoz! Hurrá! Ahhoz, hogy megértsük, mi történik a heap sort motorháztetője alatt, egy kis, rendezetlen adathalmazzal fogunk dolgozni.

Egy rendezetlen tömbtel kezdünk, amelynek öt eleme szuper rendezetlen: .

Memlékezzünk arra, hogy mivel halomrendezéssel dolgozunk, először is ezt a tömböt halommá kell alakítanunk.

Az itt látható ábrán látható, hogy a tömböt fává alakítottuk – ez még nem halom, mert még nincs semmilyen maximális vagy minimális halomsorrendben! Láthatjuk, hogy ez azért van így, mert 3 nem a legnagyobb vagy a legkisebb elem, mégis, jelenleg ez a gyökércsomópont. Ez csak egy fa, amelynek elemei a tömbből közvetlenül bináris fa formátumra vannak lefordítva.

De mivel nekünk egy max halommal kell foglalkoznunk, a struktúránkat bináris fából max halommá kell alakítanunk. Figyeljük meg, hogy a max heapben a szülő csomópontok mind nagyobbak, mint a gyermekeik. Múlt héten megtanultuk azokat az algoritmusokat, amelyek lehetővé teszik, hogy egy tömb indexéből meghatározzuk a gyermek csomópontokat; ezen a héten megnézzük őket a gyakorlatban. Ezeket az algoritmusokat használjuk arra, hogy ezt a tömböt fává, majd halommá alakítsuk.

Oké, most már van egy tényleges max halom. Nagyszerű! Most jön a tényleges munka, a rendezés.

Mivel tudjuk, hogy a legnagyobb elem a gyökércsomópontban van, tudjuk, hogy a tömb legvégére kell tennünk, az utolsó elérhető indexhelyre. Tehát felcseréljük a gyökércsomópontot az utolsó csomóponttal. Miután ezt a cserét elvégeztük, az utolsó csomópontunkban lesz a legnagyobb, maximális értékű elem.

Klassz! Most láthatjuk, hogy 19, a legnagyobb elem, amely korábban a gyökércsomópont volt, most a tömb utolsó pozíciójában van. És mivel gyakorlatilag a többi elemhez képest “rendezett”, teljesen eltávolíthatjuk a halomból.

Most a jó hír az, hogy eggyel kevesebb csomópontunk van a halomban, amit rendeznünk kell! A rossz hír? A halomunk valójában már nem is halom többé: teljesen megszegi a halom rendezési szabályát, mivel ez nem egy maximális halom. Vegyük észre, hogy 1 a gyökércsomópont, de biztosan nem nagyobb, mint két gyermekcsomópontja, 14 és 7. Tehát lefelé kell mozgatnunk a fában a megfelelő helyre.

Tegyük halmozottá ezt a fát, és tegyük újra max halommá!

Awesome! A fenti ábrán láthatjuk, hogy először a 1 és a 14, majd a 1 és a 8 értékeket cseréltük fel. Most már újra egy rendes max halomban vagyunk. Megismételhetjük ugyanazokat a lépéseket, mint a 19 elem rendezésekor:

→ Először az első és az utolsó csomópontot cseréljük fel.
→ Ezután addig halmozzuk a fát, amíg az ismét egy megfelelő max heap lesz.

Megcsináljuk ezt az új gyökércsomópontunkkal, a 14 elemmel. A következő két lépésünk így nézne ki:

Rad! Felcseréltük az első és az utolsó csomópontot, majd eltávolítottuk az utolsó csomópontot, 14, mivel az a rendezett pozíciójában volt. Ezután már csak annyit kellett tennünk, hogy a gyökércsomópontot áthelyezzük a megfelelő helyre, és addig halmozzuk az 3 elemet, amíg vissza nem kerülünk a maximális halmazállapotba.

Ezt még háromszor folytatnánk. Végül csak 1 maradna, az utolsó csomópont a halomban. Ekkor a halomrendezési algoritmus befejeződne, és tudnánk, hogy 1 lenne az első elem a tömbben, és tudnánk, hogy a tömb végre rendezett.

Itt egy remek vizualizáció az egész folyamatról, amin épp most mentünk keresztül. Figyeljük meg, hogy minden egyes iteratív rendezéssel a legnagyobb rendezetlen elem a megfelelő helyre kerül a halomban, majd a tömbben.

Heap sort: mire jó?

Amikor először olvastam a heap sortról, valami furcsán ismerős volt számomra az algoritmusban. Csak a heap sort illusztrálása után jöttem rá, honnan ered a déjà vu érzésem: a heap sort szinte pontosan olyan, mint a selection sort! Talán emlékszik a sorozat korábbi részeiből, hogy a selection sort egy olyan rendezési algoritmus, amely úgy rendezi a rendezetlen elemek listáját, hogy végigmegy az elemek listáján, megkeresi a legkisebbet, és azt félreteszi egy rendezett listába. A rendezést úgy folytatja, hogy megkeresi a legkisebb rendezetlen elemet, és hozzáadja a rendezett listához.

Nem úgy hangzik, mint a halomrendezés, csak éppen fordítva?

Kiderül, hogy a heap sort logikájában nagyon hasonlít a selection sortra: mindkét algoritmus megtalálja vagy a legkisebb vagy a legnagyobb elemet, “kiválogatja” azt, és az elemet a megfelelő helyre teszi a rendezett listában.

Amilyen hasonlóak is, a heap sort azonban egy hatalmas dologban sokkal jobb a selection sortnál: a teljesítményében! A halomrendezés alapvetően a kiválasztási rendezés szuperjavított változata. Igen, megtalálja a legnagyobb elemet egy rendezetlen gyűjteményben, és a lista végére rendezi – azonban mindezt a munkát sokkal gyorsabban végzi, mint a selection sort tenné!

Oké, de mennyivel gyorsabb a heap sort? És miért gyorsabb?

Nézzük meg a kódot. A heap sortnak különböző implementációi léteznek, az alábbi kódot a Rosetta Code heap sort JavaScript implementációjából adaptáltuk. Emlékezhetsz, hogy a heap sortnak két fontos része van: buildMaxHeap és heapify. Ezeket láthatjuk működés közben az alábbi heapSort változatban.

A buildMaxHeap függvény végzi a tényleges munkát a max heap létrehozásával. Figyeljük meg, hogy még ez a függvény is a heapify függvényt hívja, amely azt a munkát végzi, hogy egy-egy elemet lefelé mozgat a megfelelő helyre a halomban.

A heapify függvény elég fontos, ezért nézzük meg. Vegyük észre, hogy a csomópont bal és jobb gyermekének meghatározására szolgáló algoritmusokra támaszkodik, amelyeket a múlt héten tárgyaltunk, amikor először tanultunk a halmazokról.

És végül, de nem utolsósorban a swap függvény, amelyet már láttunk más rendezési algoritmusokban, de érdemes gyorsan megnézni, hogy emlékeztessük magunkat, mit csinál:

Oké, most, hogy már van némi kontextusunk arról, hogyan hatnak egymásra és hívják meg egymást ezek a függvények, térjünk vissza eredeti kérdésünkhöz, hogy hogyan és miért sokkal hatékonyabb a heap sort, mint a selection sort! Ha mélyen belenézünk a kódba, két dolgot fogunk észrevenni: először is, egyszer kell felépítenünk a maximális halmazt, átadva neki a tömb összes elemét; másodszor, a halomban lévő összes elemet újra és újra halmozni kell, kivéve az első gyökércsomópont elemét.

Ez a két megfigyelés tulajdonképpen a kulcs ahhoz a kérdéshez, hogy hogyan és miért olyan gyors a heap sort, amilyen gyors. A buildMaxHeap meghívása O(n) időt vesz igénybe, mivel minden egyes elemet hozzá kell adni a halomhoz, és a nagyobb elemszám nagyobb halmot jelent. Ne feledjük azonban, hogy bináris fával van dolgunk, és a bináris fák logaritmikus természetűek. Tehát annak ellenére, hogy újra és újra meg kell hívnunk a heapify-t, a függvény meghívása valójában meglehetősen gyors, mivel logaritmikus időben, vagyis O(log n) alatt fut le.

A két időbonyolultság kombinációját már láttuk korábban is! A halomrendezés linearitmikus időben fut, vagy Big O jelöléssel O(n log n). Tehát, annak ellenére, hogy a heap sortolás annyira hasonlít a selection sortolásra, sokkal gyorsabb! A selection sort kvadratikus időben fut, vagyis O(n²), ami sokkal kevésbé hatékony, mint a linearitmikus idő.

Nézzük meg gyorsan, hogy a heap sort milyen más módon hasonlít más rendezési algoritmusokhoz.

A heap sort a rendezés során átalakítja a neki átadott tömböt; néhány rendezési algoritmustól eltérően nem hoz létre egy teljesen külön példányt a bemeneti adatokból. Ez teszi helyben történő rendezési algoritmussá. A Heap sortnak szintén nincs szüksége külső memóriára, és belső rendezési algoritmus. Iteratívan fut (tehát nem rekurzív), és egyszerre két elemet hasonlít össze, amikor cserél és meghívja a heapify függvényt, így összehasonlító rendezési algoritmus.

A halmazok és a heapify függvény természete miatt azonban, ha vannak duplikált elemek, nem bízhatunk abban, hogy az elemek megtartják a sorrendjüket! A halomrendezés tehát instabil; ez az egyik fő különbség az egyesített rendezés és a halomrendezés között, amelyek mindegyike a fa struktúrákra támaszkodik, hogy ilyen hatékonyan működjön. A stabilitás csatájában azonban a merge sort nyer, míg a heap sort ebben a kategóriában elbukik.

A különbségek ellenére a merge sort és a heap sort egy dologban egyetérthet: bináris fák nélkül mindketten elveszettek lennének!

Források

A heap sortolásról van néhány igazán fantasztikus tanfolyami jegyzet és előadás, valamint néhány jó videós bemutató. Én azért gugliztam egy kicsit, hogy neked ne kelljen! Itt van néhány remek hely, ahol elkezdheted, ha többet szeretnél megtudni a halmazrendezésről.

1. Introduction to Algorithms: Heap Sort, MIT
2. Algorithms: Heap Sort, Professor Ching-Chi Lin
3. Heap sort, Growing with the Web
4. Heap sort in 4 minutes, Michael Sambol
5. Heap sort: Max heap, strohtennis