Heapify All The Things With Heap Sort

Vaidehi Joshi

Follow

heinäkuu 13, 2017 – 11 min read

Joku sanoi minulle kerran, että kaikki tärkeä tietotekniikassa tiivistyy puihin. Kirjaimellisesti vain puihin. Voimme käyttää niitä rakentaaksemme asioita, jäsentääksemme asioita ja tulkitaksemme asioita (kyllä, tässä saattaa tapahtua jonkin verran ennakointia, älkää huolehtiko siitä, jos siinä ei ole vielä mitään järkeä, sillä pian se on!). Ja voimme jopa käyttää niitä – arvasitkin! – lajitella asioita.

Ah, lajittelu. Olemme tehneet sitä niin paljon viime viikkoina, mutta lajitteluseikkailumme lähestyvät nyt loppuaan. On kuitenkin mahdotonta ja epäreilua puhua lajittelusta puhumatta erityisestä lajittelusta, jossa käytetään uusinta tietorakennetta tietorakennetyökaluvyössämme.

Olemme hiljattain oppineet rakastamaan kasoja, erityyppisiä binääripuita, jotka noudattavat tiukkoja sääntöjä, ja joita käytetään sellaisten asioiden kuin prioriteettijonojen ja taustatehtävien toteuttamiseen. Mutta nämä eivät ole ainoita asioita, joihin kasat ovat hyviä. Kävi ilmi, että binäärisiä kasoja käytetään usein vain tehokkaaseen lajitteluun. Monet ohjelmat tukeutuvat kasan lajitteluun, koska se on yksi tehokkaimmista tavoista lajitella joukkoja. Ja nyt kun tiedämme, mikä kasa on, voimme yrittää ymmärtää, miksi se toimii niin hyvin, kun kyse on lajittelusta!

Ennen kuin sukellamme kasan lajitteluun, varmistetaan, että meillä on kasat selvillä päässämme. Saatamme muistaa, että kasa ei oikeastaan ole mitään muuta kuin binääripuu, jossa on joitakin lisäsääntöjä, joita sen on noudatettava: ensinnäkin sillä on aina oltava kasarakenne, jossa kaikki binääripuun tasot täytetään vasemmalta oikealle, ja toiseksi sen on oltava järjestetty joko maksimikasaksi tai minikasaksi. Kasojen lajittelua varten käsittelemme yksinomaan maksimikasoja, joissa jokainen vanhemman solmu (myös juuri) on suurempi tai yhtä suuri kuin sen lapsisolmujen arvo.

Okei, vastataanpa tunnin kysymykseen: miten lajittelemme käyttämällä kasoja? No, jotta voimme vastata tuohon kysymykseen, meidän on ensin ymmärrettävä, mikä kasojen lajittelualgoritmi on!

Kasojen lajittelualgoritmi (heap sort algorithm, heap sort algoritm, heap sort algorithm) on lajittelutekniikka, joka tukeutuu binäärisiin kasoista muodostuviin datarakenteisiin. Koska tiedämme, että kasojen on aina noudatettava tiettyä järjestystä, voimme hyödyntää tätä ominaisuutta ja käyttää sitä suurimman, maksimiarvon sisältävän elementin etsimiseen ja elementtien peräkkäiseen lajitteluun valitsemalla kasan juurisolmun ja lisäämällä sen matriisin loppuun.

Tiedämme jo, että kasan lajittelu on tehokas tapa lajitella lajittelematon matriisi; mutta mitä tekemistä matriisilla on kasan kanssa? Ja miten lajittelemme joukon käyttämällä kasaa? No, on kolme keskeistä vaihetta siinä, miten tämä toimii käytännössä. Tarkastelemme niitä syvällisemmin hetken kuluttua, mutta katsotaan ensin yleistasolla, mitä nämä kolme vaihetta ovat.

1. Aluksi meillä on lajittelematon joukko. Ensimmäinen askel on ottaa tämä array ja muuttaa se kasaksi; meidän tapauksessamme haluamme muuttaa sen maksimikasaksi. Meidän on siis muunnettava ja muodostettava maksimikasa lajittelemattomasta array-datastamme. Yleensä tämä on koteloitu yhteen funktioon, jonka nimi voi olla esimerkiksi buildMaxHeap.
2. Kun meillä on array-datamme maksimikasan muodossa, voimme olla varmoja, että suurin arvo on kasan juurisolmussa. Muista, että vaikka koko kasa ei olekaan lajiteltu, jos olemme rakentaneet maksimikasamme oikein ja ilman virheitä, jokainen kasamme vanhemman solmu on arvoltaan suurempi kuin sen lapset. Siirrämme siis suurimman arvon – joka sijaitsee juurisolmussa – kasan loppuun vaihtamalla sen viimeiseen elementtiin.
3. Nyt kasan suurin elementti sijaitsee viimeisessä solmussa, mikä on hienoa. Tiedämme, että se on lajitellussa paikassaan, joten se voidaan poistaa kasasta kokonaan. Mutta on vielä yksi vaihe jäljellä: on varmistettava, että uusi juurisolmun elementti on oikeassa paikassa! On hyvin epätodennäköistä, että juurisolmun paikkaan vaihtamamme elementti on oikeassa paikassa, joten siirretään juurisolmun elementti alaspäin oikeaan paikkaan käyttämällä funktiota, jonka nimi on yleensä jotakuinkin heapify.

Ja siinä se periaatteessa onkin! Algoritmi jatkaa näiden vaiheiden toistamista, kunnes kasassa on vain yksi ainoa solmu. Siinä vaiheessa se tietää, että kaikki lajittelemattoman joukon elementit ovat lajitelluilla paikoillaan ja että viimeinen jäljellä oleva solmu on lopulta lajitellun joukon ensimmäinen elementti.

Okei, tiedän, että sanoin, että nämä ovat kasan lajittelun ainoat kolme vaihetta. Mutta jos nämä kolme vaihetta tuntuvat hämmentäviltä, älä huoli; ne voivat olla melko monimutkaisia ja vaikeasti ymmärrettäviä, kunnes näet ne toiminnassa. Itse asiassa uskon, että tämä algoritmi on paljon järkevämpi havainnollistetun esimerkin avulla. Koska kasat ovat eräänlaisia puita, niitä on helpompi visualisoida samalla tavalla kuin binääripuita. Joten tehdään se nyt!

Oletko koskaan vilkaissut kaskalajittelun konepellin alle?

Oikea, nyt on aika aloittaa absoluuttinen suosikkini kaskalajittelun oppimisessa: sen piirtäminen! Hurraa! Jotta ymmärtäisimme, mitä heap sortin konepellin alla tapahtuu, työskentelemme pienen, lajittelemattoman tietokokonaisuuden kanssa.

Aloitamme lajittelemattomalla joukolla, jossa on viisi alkiota, jotka ovat super epäjärjestyksessä: .

Muista, että koska työskentelemme kasalajittelun parissa, meidän on aluksi muutettava tämä joukko kasaksi.

Tässä kuvassa näet, että joukko on muuttunut puuksi – se ei ole vielä kasa, koska se ei ole vielä missään kasan maksimi- tai minimijärjestyksessä! Näemme, että näin on, koska 3 ei ole suurin tai pienin elementti, ja silti se on tällä hetkellä juurisolmu. Tämä on pelkkä puu, jonka elementit matriisista on käännetty suoraan binääripuun muotoon.

Mutta, koska meidän on käsiteltävä max-paalua, meidän on muutettava rakenteemme binääripuusta max-paaluksi. Huomaa, että maksimikasassa vanhemmat solmut ovat kaikki suurempia kuin niiden lapset. Viime viikolla opimme algoritmit, joiden avulla voimme määrittää lapsisolmut joukon indeksistä; tällä viikolla näemme ne käytännössä. Näiden algoritmien avulla muutamme tämän joukon ensin puuksi ja sitten kasaksi.

Okei, nyt meillä on varsinainen maksimikasa. Hienoa! Nyt varsinaiseen lajittelutyöhön.

Koska tiedämme, että suurin alkio on juurisolmussa, tiedämme, että meidän täytyy sijoittaa se matriisin ihan loppupäähän viimeiseen käytettävissä olevaan indeksipaikkaan. Vaihdamme siis juurisolmun viimeiseen solmuun. Kun teemme tämän vaihdon, viimeisessä solmussa on suurin, maksimiarvoinen elementti.

Cool! Nyt näemme, että 19, suurin elementti, joka aiemmin oli juurisolmu, on nyt viimeisellä sijalla joukossa. Ja koska se on käytännössä ”lajiteltu” suhteessa muihin elementteihin, voimme poistaa sen kokonaan kasasta.

Hyvä uutinen on nyt se, että kasassa on yksi solmu vähemmän lajiteltavana! Huono uutinen? Kasamme ei oikeastaan ole enää kasa: se rikkoo täysin kasan järjestyssääntöä, koska se ei ole maksimikasa. Huomaa, että 1 on juurisolmu, mutta se ei todellakaan ole suurempi kuin sen kaksi lapsisolmua, 14 ja 7. Meidän on siis siirrettävä se alaspäin oikealle paikalleen puussa.

Korjataan tämä puu kasaan ja tehdään siitä taas maksimikasa!

Hienoa! Yllä olevasta kuvasta näemme, että ensin vaihdoimme 1 ja 14, ja sitten vaihdoimme 1 ja 8. Nyt olemme taas kunnon maksimikasassa. Voimme toistaa samat vaiheet, jotka teimme lajitellessamme elementtiä 19:

→ Vaihdamme ensin ensimmäisen ja viimeisen solmun.
→ Sitten kasaamme puun, kunnes se on taas oikea maksimikasa.

Tehdään tämä uudella juurisolmulla, elementillä 14. Seuraavat kaksi askeleitamme näyttäisivät seuraavanlaisilta:

Rad! Vaihdoimme ensimmäisen ja viimeisen solmun, ja sitten poistimme viimeisen solmun 14, koska se oli lajitellussa paikassaan. Seuraavaksi meidän ei tarvinnut tehdä muuta kuin siirtää juurisolmu oikeaan paikkaansa ja kasata elementti 3, kunnes olimme taas maksimikasan tilassa.

Jatkoimme tätä vielä kolme kertaa. Lopulta jäljelle jäisi vain 1, kasan viimeinen solmu. Tässä vaiheessa kasan lajittelualgoritmi olisi valmis, ja tietäisimme, että 1 olisi joukon ensimmäinen elementti, ja tietäisimme, että joukko olisi vihdoin lajiteltu.

Tässä on hieno visualisointi koko prosessista, jonka juuri kävimme läpi. Huomaa, kuinka jokaisella iteratiivisella lajittelulla suurin lajittelematon alkio päätyy oikeaan paikkaansa ensin kasassa ja sitten joukossa.

Heap sort: mihin se on hyvä?

Kun luin ensimmäisen kerran heap sort -algoritmista, jokin algoritmissa tuntui oudon tutulta. Vasta havainnollistettuani heap sort -algoritmia tajusin, mistä déjà vu -tunteeni johtui: heap sort -algoritmi oli lähes täsmälleen samanlainen kuin selection sort -algoritmi! Muistat ehkä sarjan aiemmasta osasta, että valintalajittelu on lajittelualgoritmi, joka lajittelee lajittelemattomien elementtien luettelon iteroimalla elementtiluettelon läpi, etsimällä pienimmän elementin ja asettamalla sen syrjään lajiteltuun luetteloon. Se jatkaa lajittelua etsimällä pienimmän lajittelemattoman elementin ja lisäämällä sen lajiteltuun listaan.

Eikö tämä kuulosta aivan samalta kuin kasan lajittelu, mutta vain päinvastoin?

Kävi ilmi, että heap sort muistuttaa logiikaltaan paljon selection sort -lajittelua: molemmat algoritmit löytävät joko pienimmän tai suurimman elementin, ”valitsevat” sen pois ja laittavat kyseisen elementin oikeaan paikkaan lajitellussa listassa.

Niin samankaltaisia kuin ne ovatkin, heap sort on kuitenkin yhdellä massiivisella tavalla paljon parempi kuin selection sort: sen suorituskyky! Heap sort on periaatteessa superparannettu versio selection sortista. Kyllä, se etsii lajittelemattomasta kokoelmasta suurimman elementin ja järjestää sen listan loppupäähän – mutta se tekee kaiken tämän työn paljon nopeammin kuin valintalajittelu tekisi!

Okei, kuinka paljon nopeampi heapin lajittelu oikein on? Ja miksi se on nopeampi?

Katsotaanpa koodia. Heap sortista on olemassa erilaisia toteutuksia, ja alla oleva koodi on muokattu Rosetta Code:n JavaScript-toteutuksesta heap sortista. Muistat varmaan, että heap sortissa on kaksi tärkeää osaa: buildMaxHeap ja heapify. Näemme ne toiminnassa alla olevassa versiossa heapSort.

Funktio buildMaxHeap tekee sen työn, jolla itse asiassa luodaan maksimikasa. Huomaa, että tämäkin funktio kutsuu heapify-funktiota, joka tekee työn, jossa yksi elementti kerrallaan siirretään oikeaan paikkaan kasassa.

Funktio heapify on melko tärkeä, joten katsotaanpa sitä. Huomaa, että se luottaa algoritmeihin, joilla määritetään solmun vasen ja oikea lapsi, mistä keskustelimme viime viikolla, kun tutustuimme ensimmäistä kertaa kasoihin.

Ja viimeisenä, mutta ei vähäisimpänä, swap-funktio, jonka olemme nähneet ennenkin muissa lajittelualgoritmeissa, mutta jota on syytä tarkastella nopeasti muistuttaaksemme itsellemme, mitä se tekee:

Okei, nyt kun olemme saaneet jonkinlaisen kontekstin siitä, miten nämä funktiot vaikuttavat toisiinsa ja kutsuvat toisiaan, palataan alkuperäiseen kysymykseemme siitä, miten ja miksi kasan lajittelu (heap sortailu) on niin paljon tehokkaampaa kuin valintalajittelu! Jos tarkastelemme koodia syvällisesti, huomaamme kaksi asiaa: ensinnäkin, meidän on rakennettava maksimikasa kerran, jolloin kaikki matriisin elementit syötetään siihen; toiseksi, meidän on kasattava kaikki kasassa olevat elementit uudestaan ja uudestaan, lukuun ottamatta ensimmäistä juurisolmun elementtiä.

Nämä kaksi havaintoa ovat itse asiassa avain kysymykseen siitä, miten ja miksi heap sort on niin nopea kuin se on. Kutsu buildMaxHeap vie O(n) aikaa, koska jokainen yksittäinen elementti on lisättävä kasaan, ja suurempi määrä elementtejä tarkoittaa suurempaa kasaa. Muista kuitenkin, että kyseessä on binääripuu, ja binääripuut ovat luonteeltaan logaritmisia. Joten, vaikka joudumme kutsumaan heapify uudestaan ja uudestaan, tämän funktion kutsuminen on itse asiassa melko nopeaa, koska se suoritetaan logaritmisessa ajassa eli O(log n).

Tämän kahden aikakompleksisuuden yhdistelmä on jotakin, minkä olemme nähneet jo aiemmin! Kasojen lajittelu toimii lineaaritermisessä ajassa, tai Big O -merkinnällä O(n log n). Joten, vaikka heap sort näyttää niin paljon samalta kuin selection sort, se on paljon nopeampi! Valintalajittelu toimii kvadraattisessa ajassa eli O(n²), mikä on paljon tehottomampaa kuin lineaaritminen aika.

Katsotaanpa nopeasti muita tapoja, joilla heap sort vertautuu muihin lajittelualgoritmeihin.

Heap sort muuttaa sille välitettävän joukon lajitellessaan; toisin kuin jotkin lajittelualgoritmit, se ei luo syöttödatasta täysin erillistä kopiota. Tämä tekee siitä paikan sisäisen lajittelualgoritmin. Heap sort ei myöskään tarvitse ulkoista muistia, vaan se on sisäinen lajittelualgoritmi. Se suoritetaan iteratiivisesti (ja on siten ei-rekursiivinen), ja se vertaa kahta elementtiä kerrallaan vaihtaessaan ja kutsuessaan heapify-funktiota, mikä tekee siitä vertailulajittelualgoritmin.

Haapojen ja heapify-funktion luonteen vuoksi emme kuitenkaan voi luottaa siihen, että elementit säilyttävät järjestyksensä, jos elementtejä on päällekkäin! Tämä on merkittävä ero yhdistelmälajittelun ja kaskalajittelun välillä, jotka molemmat tukeutuvat puurakenteisiin toimiakseen niin tehokkaasti. Merge sort voittaa kuitenkin taistelun vakaudesta, kun taas heap sort epäonnistuu tässä kategoriassa.

Eroistaan huolimatta merge sort ja heap sort voivat olla yhtä mieltä yhdestä asiasta: ilman binääripuita molemmat olisivat hukassa!

Lähteet

Haapalajittelusta on olemassa todella loistavia kurssin muistiinpanoja ja luentoja sekä muutama hyvä video-opetusohjelma. Tein vähän googlettamista, jotta sinun ei tarvitsisi! Tässä on muutamia loistavia paikkoja, joista voit aloittaa, jos olet kiinnostunut oppimaan lisää kasojen lajittelusta.

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