Heapsort
Heapsort is selection sort met een betere manier om de grootste waarde te vinden. Het houdt de ongesorteerde waarden in een heap, een boom die in de lijst zelf staat, met de grootste waarde altijd bovenaan. Die eraf halen en de heap herstellen kost ongeveer log n stappen in plaats van de hele lijst door te lopen.
Een boom in een lijst
Een binaire heap is een boom zonder pointers. Positie 0 is de wortel, en de kinderen van positie i zijn posities 2i + 1 en 2i + 2. Posities 1 en 2 zijn dus de kinderen van de wortel, posities 3 tot 6 het volgende niveau, enzovoort. Elk niveau is vol behalve het laatste, dat van links wordt gevuld. In een max-heap is elke ouder minstens zo groot als zijn kinderen, dus de grootste waarde staat altijd in de wortel.
Laten zakken
Eén bewerking doet al het werk. Om een waarde te laten zakken, vergelijk je haar met haar kinderen. Is het grootste kind groter dan de waarde, dan wisselen ze, en wordt de waarde vergeleken met haar nieuwe kinderen. Het stopt als geen kind groter is, of als de waarde onderaan is. Omdat de boom maar ongeveer log₂ n niveaus heeft, kost zakken hooguit ongeveer 2 log₂ n vergelijkingen.
Eerst de heap bouwen, dan sorteren
Om de heap te bouwen laat je elke ouder zakken, van de laatste terug naar de wortel. Elke deelboom is al een heap voordat zijn ouder erin zakt. Sorteer dan: wissel de wortel, de grootste waarde, met de laatste waarde van de heap. Die waarde staat nu op haar definitieve plek. De heap is één korter, en de waarde die in de wortel belandt, zakt omlaag om de heap te herstellen. Herhaal tot er één waarde over is.
Een voorbeeld
Neem 5, 1, 4, 2, 8. Bij het bouwen van de heap zakt 1 onder 8, daarna zakt 5 onder 8, wat 8, 5, 4, 2, 1 geeft. Nu wisselt 8 naar het eind; 1 belandt in de wortel en zakt langs 5 en 2: 5, 2, 4, 1 | 8. Dan gaat 5 naar het eind en zakt 1 langs 4: 4, 2, 1 | 5, 8. Nog twee rondes maken de lijst af: 1, 2, 4, 5, 8, na 12 vergelijkingen en 10 verwisselingen.
Sterke en zwakke punten
Heapsort kost tijd evenredig met n log n, ook in het slechtste geval, en heeft geen extra geheugen nodig. Quicksort kan vertragen tot n² en mergesort heeft een buffer zo lang als de lijst nodig, dus heapsort is de veilige terugvaloptie: introsort, gebruikt door de standaardbibliotheek van C++, schakelt erop over als de partities van quicksort misgaan. Op echte computers is het meestal trager dan allebei, omdat het tussen verre plekken in de lijst springt, en het is niet stabiel. J. W. J. Williams publiceerde heapsort, samen met de binaire heap, in 1964.
Probeer het zelf
Open de app en druk op Stap. De boom boven de staven toont de heap: de waarde die zakt heeft een eigen kleur, het kind waarmee ze wordt vergeleken licht op, en elke verwisseling is te zien in zowel de boom als de staven. Zodra de heap klaar is, zie je de wortel naar het eind wisselen, groen worden en uit de boom verdwijnen.
Veelgestelde vragen
Wat is de tijdscomplexiteit van heapsort?
O(n log n) in het beste, gemiddelde en slechtste geval. De heap bouwen kost O(n), en elk van de n − 1 keer uithalen kost O(log n). Het sorteert in-place met O(1) extra geheugen.
Wat is het verschil tussen heapsort en selection sort?
Beide pakken steeds de grootste (of kleinste) overgebleven waarde. Selection sort zoekt die door het ongesorteerde deel helemaal te doorlopen, elke keer n vergelijkingen. Heapsort houdt het ongesorteerde deel in een heap, waar de grootste waarde al bovenaan staat, en de heap herstellen kost maar ongeveer log n vergelijkingen.
Waarvoor wordt een heap nog meer gebruikt?
Prioriteitswachtrijen: een heap geeft meteen het grootste (of kleinste) element en laat je elementen toevoegen of verwijderen in ongeveer log n stappen. Planners, het kortstepadalgoritme van Dijkstra en eventsimulaties gebruiken er allemaal een.
Is heapsort stabiel?
Nee. Door de wortel naar het eind te wisselen gaan waarden over grote afstanden, dus gelijke waarden kunnen van volgorde veranderen.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer heapsort