Hæv alle ting med Heap Sort
Nogen fortalte mig engang, at alt vigtigt inden for datalogi kan koges ned til træer. Bogstaveligt talt bare træer. Vi kan bruge dem til at bygge ting, analysere ting og fortolke ting (ja, der sker måske en vis forspiring her, men du skal ikke bekymre dig om det, hvis det ikke giver nogen mening for dig endnu, for det vil det snart gøre!) Og vi kan endda bruge dem til at – du gættede det! – at sortere ting.
Ah, sortering. Vi har gjort så meget af det i de sidste par uger, men vi nærmer os nu afslutningen på vores sorteringseventyr. Det er dog umuligt og uretfærdigt at tale om sortering uden at tale om en særlig form for sortering, der bruger den nyeste datastruktur i vores datastrukturværktøjsbælte.
Vi har for nylig lært at elske heaps, en særlig form for binært træ, der følger et strengt sæt regler, og som bruges til at implementere ting som prioritetskøer og baggrundsjobs. Men det er ikke de eneste ting, som heaps er gode til. Det viser sig, at binære heaps ofte bruges til intet andet formål end effektiv sortering. Mange programmer vil være afhængige af heap-sortering, da det tilfældigvis er en af de mest effektive måder at sortere et array på. Og nu hvor vi ved, hvad en heap er, kan vi forsøge at forstå, hvorfor den fungerer så godt, når det drejer sig om problemet med sortering!
Hvor vi dykker ned i heap sort, skal vi sikre os, at vi har heaps lige i hovedet. Vi kan huske, at en heap egentlig ikke er andet end et binært træ med nogle ekstra regler, som den skal følge: For det første skal den altid have en heap-struktur, hvor alle niveauer i det binære træ er fyldt op fra venstre mod højre, og for det andet skal den enten være ordnet som en max heap eller en min heap. I forbindelse med heap-sortering vil vi udelukkende beskæftige os med max-heaps, hvor alle forældreknuder (inklusive roden) er større end eller lig med værdien af deres børneknuder.
Okay, lad os komme til at besvare dagens spørgsmål: Hvordan sorterer vi ved hjælp af heaps? Nå, men for at kunne besvare det spørgsmål skal vi først forstå, hvad en heap-sorteringsalgoritme er!
En heap-sorteringsalgoritme er en sorteringsteknik, der læner sig op ad binære heap-datastrukturer. Fordi vi ved, at heaps altid skal følge en bestemt rækkefølge, kan vi udnytte denne egenskab og bruge den til at finde det største element med maksimal værdi og sortere elementerne sekventielt ved at vælge rodknuden i en heap og tilføje den til enden af arrayet.
Vi ved allerede, at heap-sortering er en effektiv måde at sortere et usorteret array på; men hvad har et array med en heap at gøre? Og hvordan sorterer vi et array ved hjælp af en heap? Tja, der er tre vigtige trin for, hvordan dette rent faktisk fungerer i praksis. Vi vil se nærmere på disse om et øjeblik, men lad os først tage et overordnet blik på, hvad disse tre trin er.
- Til at begynde med har vi et usorteret array. Det første skridt er at tage dette array og lave det om til en heap; i vores tilfælde vil vi lave det om til en max heap. Vi skal altså transformere og opbygge en max heap ud fra vores usorterede array-data. Normalt er dette indkapslet af en enkelt funktion, som kan hedde noget i retning af
buildMaxHeap. - Når vi har vores array-data i et max heap-format, kan vi være sikre på, at den største værdi befinder sig ved rodknuden i heap’en. Husk, at selv om hele heap’en ikke vil være sorteret, vil hver enkelt moderknude i vores heap være større i værdi end dens børn, hvis vi har opbygget vores max heap korrekt og uden fejl. Så vi flytter den største værdi – som befinder sig ved rodknuden – til enden af bunken ved at bytte den med det sidste element.
- Nu befinder det største element i bunken sig ved den sidste knude, hvilket er fantastisk. Vi ved, at det befinder sig i sin sorterede position, så det kan fjernes helt fra bunken. Men der er stadig et skridt mere: at sikre, at det nye rodknudeelement er på den rigtige plads! Det er højst usandsynligt, at det element, som vi har byttet ind i rodknudepositionen, er på den rigtige plads, så vi flytter rodknudeelementet ned til den rigtige plads ved hjælp af en funktion, der normalt hedder noget i retning af
heapify.
Og det er stort set det hele! Algoritmen fortsætter med at gentage disse trin, indtil bunken er nede på kun en enkelt knude. På det tidspunkt ved den, at alle elementer i det usorterede array er på deres sorterede positioner, og at det sidste tilbageværende knudepunkt vil ende med at være det første element i det sorterede array.
Okay, jeg ved godt, at jeg sagde, at dette er de eneste tre trin i heap-sortering. Men hvis disse tre trin virker forvirrende, skal du ikke bekymre dig; de kan være ret komplicerede og svære at forstå, indtil du ser dem udspille sig i praksis. Faktisk synes jeg, at denne algoritme giver meget mere mening med et illustreret eksempel. Da heaps er en type træ, hjælper det at visualisere dem, på samme måde som vi gør med binære træer. Så lad os gøre det lige nu!
Har du nogensinde kigget under heap sorteringens hætte?
Okay, det er tid til min absolut yndlingsdel af at lære heap sortering: at tegne den ud! Hurra! For at forstå, hvad der foregår under heap sort-hætten, arbejder vi med et lille, usorteret datasæt.
Vi starter med et usorteret array med fem elementer, der er super uordnede: .
Husk, at da det er heap-sortering, vi arbejder med, skal vi til at begynde med forvandle arrayet til en heap.
I illustrationen her kan du se, at arrayet er blevet forvandlet til et træ – det er ikke en heap endnu, for det er stadig ikke i nogen max- eller min-heap-orden! Vi kan se, at dette er tilfældet, fordi 3 ikke er det største eller mindste element, og alligevel er det rodknuden i øjeblikket. Dette er bare et træ, hvor elementerne fra arrayet er direkte oversat til et binært træformat.
Men da vi skal håndtere en max heap, skal vi omdanne vores struktur fra et binært træ til en max heap. Læg mærke til, at i max heap’en er de overordnede knuder alle større end deres børn. I sidste uge lærte vi de algoritmer, der gør det muligt for os at bestemme barnknuderne ud fra indekset i et array; i denne uge skal vi se dem i aktion. Det er disse algoritmer, vi bruger til at omdanne dette array til et træ og derefter til en bunke.
Okay, nu har vi en egentlig max heap. Fedt! Nu til det egentlige arbejde med at sortere.
Da vi ved, at det største element befinder sig ved rodknuden, ved vi, at vi skal placere det helt i slutningen af arrayet, på den sidste ledige indekspost. Så vi bytter rodknuden ud med den sidste knude. Når vi foretager denne ombytning, vil vores sidste knude indeholde det største element med maks. værdi.
Cool! Nu kan vi se, at 19, det største element, som tidligere var rodknuden, nu befinder sig på den sidste position i arrayet. Og da det effektivt er “sorteret” i forhold til resten af elementerne, kan vi fjerne det helt fra bunken.
Nu er den gode nyhed, at vi har en knude mindre i vores bunke, som vi skal sortere! Den dårlige nyhed? Vores heap er faktisk ikke længere en heap: den overtræder totalt sin heap-ordningsregel, da den ikke er en max-heap. Bemærk, at 1 er rodknuden, men den er bestemt ikke større end dens to barnknuder, 14 og 7. Så vi skal flytte den ned til dens korrekte plads i træet.
Lad os heapificere dette træ og gøre det til en max heap igen!
Awesome! I illustrationen ovenfor kan vi se, at vi først byttede 1 og 14, og derefter byttede vi 1 og 8. Nu er vi tilbage til en rigtig max heap. Vi kan gentage de samme trin, som vi gjorde, da vi sorterede elementet 19:
→ Vi bytter først den første og den sidste knude.
→ Derefter heapificerer vi træet, indtil det igen er en rigtig max heap.
Lad os gøre det med vores nye rodknude, elementet 14. Sådan ville vores næste to trin se ud:
Rad! Vi byttede den første og den sidste knude, og derefter fjernede vi den sidste knude, 14, da den var i den sorterede position. Det eneste, vi nu skulle gøre, var at flytte rodknuden til dens korrekte placering og heapificere elementet 3, indtil vi var tilbage i en max heap-tilstand.
Vi ville fortsætte med at gøre dette tre gange mere. Til sidst ville vi kun være tilbage med 1, det sidste knudepunkt i heap’en. På dette tidspunkt ville heap-sorteringsalgoritmen være færdig, og vi ville vide, at 1 ville være det første element i arrayet, og vi ville vide, at arrayet endelig var sorteret.
Her er en god visualisering af hele den proces, vi lige har gennemgået. Læg mærke til, hvordan det største usorterede element ved hver iterativ sortering ender på sin rette plads i bunken og derefter i arrayet.
Heap sort: what is it good for?
Da jeg første gang læste om heap sort, var der noget ved algoritmen, der virkede mærkeligt bekendt for mig. Det var først efter at have illustreret heap sort, at det gik op for mig, hvor min følelse af déjà vu kom fra: heap sort var næsten nøjagtig som selection sort! Du husker måske fra tidligere i serien, at selection sort er en sorteringsalgoritme, der sorterer en liste af usorterede elementer ved at iterere gennem en liste af elementer, finde det mindste element og sætte det til side i en sorteret liste. Den fortsætter med at sortere ved at finde det mindste usorterede element og tilføje det til den sorterede liste.
Lyder det ikke meget som heap sort, men bare omvendt?
Det viser sig, at heap sort ligner selektionssortering meget i sin logik: begge algoritmer finder enten det mindste eller største element, “vælger” det ud og placerer dette element på sin korrekte plads i den sorterede liste.
Men uanset hvor ens de er, er heap sort meget bedre end selektionssortering på én massiv måde: dens ydeevne! Heap sort er grundlæggende en superforbedret version af selection sort. Ja, den finder det største element i en usorteret samling og ordner det bagerst på listen – men den gør alt dette arbejde så meget hurtigere end selection sort ville gøre!
Okay, så hvor meget hurtigere er heap sort egentlig? Og hvorfor er det hurtigere?
Jamen, lad os tage et kig på koden. Der findes forskellige implementeringer af heap sort, og koden nedenfor er tilpasset Rosetta Code’s JavaScript-implementering af heap sort. Du vil huske, at heap sort har to vigtige dele: buildMaxHeap og heapify. Vi kan se dem i aktion i nedenstående version af heapSort.
Funktionen buildMaxHeap udfører arbejdet med at oprette den faktiske max heap. Bemærk, at selv denne funktion kalder på heapify, som udfører arbejdet med at flytte et element ad gangen ned til dets korrekte placering i heap’en.
Funktionen heapify er ret vigtig, så lad os se på den. Bemærk, at den er afhængig af algoritmerne til at bestemme venstre og højre barn af en node, hvilket vi diskuterede i sidste uge, da vi først lærte om heaps.
Og sidst, men ikke mindst, funktionen swap, som vi har set før i andre sorteringsalgoritmer, men som er værd at kigge hurtigt på for at minde os selv om, hvad den gør:
Okay, nu hvor vi har fået lidt kontekst for, hvordan disse funktioner interagerer og påkalder hinanden, så lad os vende tilbage til vores oprindelige spørgsmål om, hvordan og hvorfor heap sortering er så meget mere effektiv end selektionssortering! Hvis vi kigger dybt i koden, vil vi bemærke to ting: For det første skal vi opbygge max-heap’en én gang, idet vi overfører alle arrayets elementer til den; for det andet skal vi heapificere alle elementerne i heap’en igen og igen, med undtagelse af det første rodknudeelement.
Disse to observationer er faktisk nøglen til spørgsmålet om, hvordan og hvorfor heap sort er så hurtig, som den er. Det tager O(n) tid at kalde buildMaxHeap, da hvert enkelt element skal tilføjes til bunken, og et større antal elementer betyder en større bunke. Husk dog, at vi har at gøre med et binært træ, og binære træer er logaritmiske i deres natur. Så selv om vi skal kalde heapify igen og igen, er det faktisk ret hurtigt at påkalde denne funktion, da den vil køre på logaritmisk tid, eller O(log n).
Kombinationen af disse to tidskompleksiteter er noget, vi allerede har set før! Heap sort kører i lineæritmisk tid, eller i Big O notation, O(n log n). Så selv om heap sort ligner selection sort i høj grad, er den meget hurtigere! Selection sort kører i kvadratisk tid, eller O(n²), hvilket er så meget mindre effektivt end lineæritmisk tid.
Lad os hurtigt se på de andre måder, hvorpå heap sort kan sammenlignes med andre sorteringsalgoritmer.
Heap sort transformerer det array, der overgives til den, mens den sorterer; i modsætning til nogle sorteringsalgoritmer opretter den ikke en helt separat kopi af inddataene. Dette gør den til en sorteringsalgoritme, der sorterer på stedet. Heap sort har heller ikke brug for ekstern hukommelse, og er en intern sorteringsalgoritme. Den kører iterativt (og er således ikke-rekursiv) og sammenligner to elementer ad gangen, når den bytter og kalder heapify-funktionen, hvilket gør den til en sammenlignings-sorteringsalgoritme.
Men på grund af arten af heaps og heapify-funktionen kan vi ikke regne med, at elementerne bevarer deres rækkefølge, hvis der er dublerede elementer! Heap sort er altså ustabilt; dette er en vigtig forskel mellem merge sort og heap sort, som begge er afhængige af træstrukturer for at kunne fungere effektivt. Merge sort vinder dog i kampen om stabilitet, mens heap sort fejler i denne kategori.
Trods deres forskelle kan merge sort og heap sort blive enige om én ting: uden binære træer ville de begge være tabt!
Ressourcer
Der findes nogle virkelig fantastiske kursusnoter og foredrag om heap sorting, samt et par gode videovejledninger. Jeg har googlet lidt, så du ikke behøver at gøre det! Her er nogle gode steder at starte, hvis du er interesseret i at lære mere om heap sort.
- Introduction to Algorithms: Heap Sort, MIT
- Algorithms: Heap Sort, Professor Ching-Chi Lin
- Heap sort, Growing with the Web
- Heap sort in 4 minutes, Michael Sambol
- Heap sort: Max heap, strohtennis
Leave a Reply