Högsortera alla saker med Heap Sort
Någon sa en gång till mig att allt viktigt inom datavetenskap kokar ner till träd. Bokstavligen bara träd. Vi kan använda dem för att bygga saker, analysera saker och tolka saker (ja, det kan hända att det sker en viss förebådelse här, oroa dig inte för det om det inte verkar vettigt för dig ännu, för snart kommer det att göra det!) Och vi kan till och med använda dem för att – du gissade det! – sortera saker.
Ah, sortering. Vi har gjort så mycket av det under de senaste veckorna, men vi närmar oss nu slutet på våra sorteringsäventyr. Det är dock omöjligt och orättvist att tala om sortering utan att tala om en speciell sorts sortering som använder den senaste datastrukturen i vårt verktygsbälte för datastrukturer.
Vi har nyligen lärt oss att älska heaps, en speciell sorts binärt träd som följer en strikt uppsättning regler, och som används för att implementera saker som prioriterade köer och bakgrundsjobb. Men detta är inte de enda saker som heaps är bra för. Det visar sig att binära heaps ofta används för inget annat ändamål än effektiv sortering. Många program kommer att förlita sig på heap-sortering eftersom det råkar vara ett av de mest effektiva sätten att sortera en array. Och nu när vi vet vad en heap är kan vi försöka förstå varför den fungerar så bra när det gäller problemet med sortering!
Innan vi dyker ner i heap sort ska vi se till att vi har heaps rätt i huvudet. Vi kanske kommer ihåg att en heap egentligen inte är något annat än ett binärt träd med några ytterligare regler som den måste följa: för det första måste den alltid ha en heap-struktur, där alla nivåer i det binära trädet fylls upp, från vänster till höger, och för det andra måste den antingen vara ordnad som en max heap eller en min heap. När det gäller heap-sortering kommer vi uteslutande att ha att göra med max heaps, där varje föräldraknut (inklusive roten) är större än eller lika med värdet på dess barnknutar.
Okej, låt oss börja besvara dagens fråga: hur sorterar vi med hjälp av heaps? För att kunna svara på den frågan måste vi först förstå vad en heap-sorteringsalgoritm är!
En heap-sorteringsalgoritm är en sorteringsteknik som bygger på binära heap-datastrukturer. Eftersom vi vet att heaps alltid måste följa en viss ordning kan vi utnyttja den egenskapen och använda den för att hitta det största elementet med maximalt värde och sekventiellt sortera element genom att välja rotnoden i en heap och lägga till den i slutet av matrisen.
Vi vet redan att heap-sortering är ett effektivt sätt att sortera en osorterad matris, men vad har en matris med en heap att göra? Och hur sorterar vi en array med hjälp av en heap? Tja, det finns tre viktiga steg för hur detta faktiskt fungerar i praktiken. Vi kommer att titta närmare på dessa om en stund, men låt oss först ta en översiktlig titt på vad dessa tre steg är.
- För att börja har vi en osorterad array. Det första steget är att ta den arrayen och förvandla den till en heap; i vårt fall vill vi förvandla den till en max heap. Vi måste alltså omvandla och bygga en max heap av våra osorterade array-data. Vanligtvis kapslas detta in av en enda funktion, som kan heta något i stil med
buildMaxHeap. - När vi väl har våra array-data i ett max heap-format kan vi vara säkra på att det största värdet finns vid rotnoden i heap:en. Kom ihåg att även om hela högen inte kommer att vara sorterad, om vi har byggt vår max heap på rätt sätt och utan några misstag, kommer varje enskild modernod i vår höge att vara större i värde än sina barn. Så vi flyttar det största värdet – som ligger i rotnoden – till slutet av högen genom att byta ut det med det sista elementet.
- Nu ligger det största elementet i högen i den sista noden, vilket är bra. Vi vet att den befinner sig i sin sorterade position, så den kan tas bort från högen helt och hållet. Men det återstår fortfarande ett steg: att se till att det nya elementet i rotnoden befinner sig på rätt plats! Det är högst osannolikt att det element som vi bytte in i rotnodspositionen är på rätt plats, så vi flyttar ner rotnodelementet ner till rätt plats, med hjälp av en funktion som vanligtvis heter något i stil med
heapify.
Och det är i princip allt! Algoritmen fortsätter att upprepa dessa steg tills högen är nere på bara en enda nod. Vid den tidpunkten vet den att alla element i den osorterade matrisen är i sina sorterade positioner och att den sista kvarvarande noden kommer att sluta med att vara det första elementet i den sorterade matrisen.
Okej, jag vet att jag sa att det här är de enda tre stegen för att sortera en hög. Men om dessa tre steg verkar förvirrande behöver du inte oroa dig; de kan vara ganska komplicerade och svåra att förstå tills du ser dem i praktiken. Faktum är att jag tycker att den här algoritmen blir mycket mer begriplig med ett illustrerat exempel. Eftersom heaps är en typ av träd hjälper det att visualisera dem, på samma sätt som vi gör med binära träd. Så låt oss göra det nu!
Har du någonsin tittat under huven på heap sort?
Okej, det är dags för min absoluta favoritdel av att lära sig heap sort: att rita upp den! Hurra! För att förstå vad som händer under huven på heap sort ska vi arbeta med ett litet osorterat dataset.
Vi börjar med en osorterad array med fem element som är super oordnade: .
Håll i minnet att eftersom det är heap-sortering vi arbetar med måste vi förvandla arrayen till en heap till att börja med.
I illustrationen som visas här kan du se att arrayen har förvandlats till ett träd – det är inte en heap ännu eftersom den fortfarande inte har någon max- eller min-ordning i heap! Vi kan se att detta är fallet eftersom 3 inte är det största eller minsta elementet, och ändå är det rotnoden för tillfället. Detta är bara ett träd, med elementen från arrayen direkt översatta till ett binärt trädformat.
Men eftersom vi måste hantera en max heap måste vi omvandla vår struktur från ett binärt träd till en max heap. Lägg märke till att i max heap är alla föräldernoderna större än deras barn. Förra veckan lärde vi oss algoritmerna som gör att vi kan bestämma barnnoderna från indexet i en array; den här veckan ser vi dem i praktiken. Det är dessa algoritmer som vi använder för att omvandla denna array till ett träd och sedan till en heap.
Okej, nu har vi en riktig max heap. Bra! Nu till själva sorteringsarbetet.
Då vi vet att det största elementet finns i rotnoden, vet vi att vi måste placera det längst ut i matrisen, på den sista tillgängliga indexplatsen. Så vi byter ut rotnoden mot den sista noden. När vi gör detta byte kommer vår sista nod att innehålla det största elementet med maxvärde.
Cool! Nu kan vi se att 19, det största elementet, som tidigare var rotnoden, nu befinner sig på den sista positionen i matrisen. Och eftersom den i praktiken är ”sorterad” i förhållande till resten av elementen kan vi ta bort den helt från högen.
Nu är den goda nyheten att vi har en nod mindre i vår höge att sortera! Den dåliga nyheten? Vår heap är faktiskt inte längre en heap: den bryter helt mot regeln för heapordning, eftersom den inte är en maxheap. Observera att 1 är rotnoden, men den är definitivt inte större än dess två barnnoder, 14 och 7. Så vi måste flytta ner den till sin rätta plats i trädet.
Låt oss heapifiera det här trädet och göra det till en max heap igen!
Awesome! I illustrationen ovan kan vi se att vi först bytte 1 och 14 och sedan 1 och 8. Nu är vi tillbaka till en riktig maxheap. Vi kan upprepa samma steg som vi gjorde när vi sorterade elementet 19:
→ Vi byter först ut den första och sista noden.
→ Sedan heapifierar vi trädet tills det är en riktig maxheap igen.
Låt oss göra det med vår nya rotnod, elementet 14. Så här skulle våra nästa två steg se ut:
Rad! Vi bytte ut den första och sista noden, och sedan tog vi bort den sista noden, 14, eftersom den var i sin sorterade position. Det enda vi behövde göra härnäst var att flytta rotnoden till sin rätta plats och heapifiera elementet 3 tills vi var tillbaka i ett max heap-tillstånd.
Vi skulle fortsätta att göra detta tre gånger till. Till slut skulle vi bara ha kvar 1, den sista noden i högen. Vid denna tidpunkt skulle heap-sorteringsalgoritmen vara klar, och vi skulle veta att 1 skulle vara det första elementet i arrayen, och vi skulle veta att arrayen äntligen var sorterad.
Här är en bra visualisering av hela processen som vi just gick igenom. Lägg märke till hur det största osorterade elementet med varje iterativ sortering hamnar på rätt plats i högen och sedan i arrayen.
Heap sort: what is it good for?
När jag läste om heap sort för första gången, var det något med algoritmen som kändes märkligt bekant för mig. Det var först efter att ha illustrerat heap sort som jag insåg varifrån min känsla av déjà vu kom: heap sort var nästan exakt som selection sort! Du kanske minns från tidigare i serien att urvalssortering är en sorteringsalgoritm som sorterar en lista med osorterade objekt genom att iterera genom en lista med element, hitta det minsta elementet och lägga det åt sidan i en sorterad lista. Den fortsätter att sortera genom att hitta det minsta osorterade elementet och lägga till det i den sorterade listan.
Låter det inte väldigt likt heap sort, men bara omvänt?
Det visar sig att heap sort är mycket lik selektionssortering i sin logik: båda algoritmerna hittar antingen det minsta eller största elementet, ”väljer” ut det och placerar det elementet på rätt plats i den sorterade listan.
Men hur lika de än är, är heap sort mycket bättre än selektionssortering på ett massivt sätt: dess prestanda! Heap sort är i princip en superförbättrad version av selection sort. Ja, den hittar det största elementet i en osorterad samling och ordnar det längst bak i listan – men den gör allt detta arbete mycket snabbare än vad urvalssortering skulle göra!
Okej, men hur mycket snabbare är högsortering egentligen? Och varför är det snabbare?
Vi tar en titt på koden. Det finns olika implementeringar av heap sort, och koden nedan är anpassad från Rosetta Codes JavaScript-implementering av heap sort. Du kommer ihåg att heap sort har två viktiga delar: buildMaxHeap och heapify. Vi kan se dem i aktion i versionen av heapSort nedan.
Funktionen buildMaxHeap gör arbetet med att faktiskt skapa max heap. Lägg märke till att även denna funktion anropar heapify, som gör arbetet med att flytta ett element i taget ner till sin rätta plats i heap.
Funktionen heapify är ganska viktig, så låt oss titta på den. Lägg märke till att den förlitar sig på algoritmerna för att bestämma en nodens vänstra och högra barn, vilket vi diskuterade förra veckan när vi först lärde oss om heaps.
Och sist men inte minst funktionen swap, som vi har sett tidigare i andra sorteringsalgoritmer, men som är värd att titta på snabbt för att påminna oss om vad den gör:
Okej, nu när vi har fått en viss kontext för hur dessa funktioner interagerar och anropar varandra, så låt oss återgå till vår ursprungliga fråga, nämligen hur och varför heap-sortering är så mycket effektivare än selection sort! Om vi tittar djupt i koden märker vi två saker: för det första måste vi bygga max heap en gång och skicka in alla element i arrayen till den, för det andra måste vi heapifiera alla element i heapet om och om igen, med undantag för det första elementet i rotnoden.
Dessa två observationer är faktiskt nyckeln till frågan om hur och varför heap sort är så snabb som den är. Att kalla buildMaxHeap tar O(n) tid, eftersom varje enskilt element måste läggas till i högen, och ett större antal element innebär en större höge. Kom dock ihåg att vi har att göra med ett binärt träd, och binära träd är logaritmiska till sin natur. Så även om vi måste anropa heapify om och om igen är det faktiskt ganska snabbt att åberopa denna funktion, eftersom den kommer att köras på logaritmisk tid, eller O(log n).
Kombinationen av dessa två tidskomplexiteter är något som vi redan har sett förut! Heap sort körs på linjäritmisk tid, eller i Big O-notation, O(n log n). Så även om heap sort ser ut så mycket som selection sort är den mycket snabbare! Selektionssortering körs i kvadratisk tid, eller O(n²), vilket är så mycket mindre effektivt än linjäritmisk tid.
Låt oss snabbt titta på de andra sätten som heap sort jämförs med andra sorteringsalgoritmer.
Heap sort omvandlar arrayen som passerar till den när den sorterar; till skillnad från vissa sorteringsalgoritmer skapar den inte en helt separat kopia av indatadata. Detta gör den till en sorteringsalgoritm på plats. Heap sort behöver inte heller externt minne och är en intern sorteringsalgoritm. Den körs iterativt (och är således inte rekursiv) och jämför två element i taget när den byter och anropar heapify-funktionen, vilket gör den till en jämförelsesorteringsalgoritm.
På grund av heaps och heapify-funktionens natur kan vi dock inte lita på att elementen behåller sin ordning om det finns dubbla element, om det finns dubbla element! Heap sort är alltså instabil; detta är en viktig skillnad mellan merge sort och heap sort, som båda förlitar sig på trädstrukturer för att fungera så effektivt. Merge sort vinner dock i slaget om stabilitet, medan heap sort misslyckas i denna kategori.
Trots sina olikheter kan merge sort och heap sort enas om en sak: utan binära träd skulle båda vara förlorade!
Resurser
Det finns några riktigt fantastiska kursanteckningar och föreläsningar om heap sorting, samt ett par bra videohandledningar. Jag googlade lite så att du inte skulle behöva göra det! Här är några bra ställen att börja om du är intresserad av att lära dig mer 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