- Zakt omlaag
- Vergeleken
- Verwisseld
- Op zijn plek
Heapsort
Heapsort leest de lijst als binaire boom en zet die om in een max-heap, waarin elke ouder minstens zo groot is als zijn kinderen. De grootste waarde staat dan bovenaan. Wissel die naar het eind, waar ze blijft, herstel de heap en herhaal. De app tekent de heap als boom boven de staven, zodat je elke waarde kunt volgen terwijl ze omlaag zakt. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De boom boven de staven toont dezelfde waarden als heap. De tegels tellen vergelijkingen, verwisselingen en de waarden die uit de heap zijn gehaald. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
- Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
- Kijk naar de boom: eerst zakt elke ouder omlaag tot de heap klaar is, daarna wisselt de wortel naar het eind en wordt de heap één kleiner.
Zo werkt heapsort
Lees de lijst als boom: de waarde op positie i heeft haar kinderen op posities 2i + 1 en 2i + 2. Bouw een max-heap door elke ouder te laten zakken, te beginnen bij de laatste ouder: zolang een waarde kleiner is dan haar grootste kind, wisselen de twee. Als de wortel de grootste waarde heeft, wissel je die met de laatste waarde van de heap. Die waarde staat nu definitief, de heap is één korter, en de nieuwe wortel zakt omlaag zodat het weer een heap is. Herhaal tot de heap leeg is.
Altijd n log n, in-place
De boom heeft ongeveer log₂ n niveaus, dus elke keer zakken kost hooguit ongeveer 2 log₂ n vergelijkingen, en het bouwen van de heap minder dan 2n. Zo doet heapsort in het slechtste geval ongeveer 2n log₂ n vergelijkingen, zonder buffer: bij 40 waarden hooguit 352. Anders dan quicksort heeft het geen slechte invoer, en anders dan mergesort heeft het geen extra geheugen nodig. In de praktijk is het meestal trager dan allebei, omdat het door de lijst springt, en het is niet stabiel.
Veelgestelde vragen
Hoe werkt heapsort?
Het zet de lijst om in een max-heap, een boom die in de lijst zelf staat en waarin elke ouder minstens zo groot is als zijn kinderen. Daarna wisselt het steeds de grootste waarde, in de wortel, naar het eind van de heap en laat het de nieuwe wortel zakken om de heap te herstellen.
Wat is een heap?
Een complete binaire boom die zonder pointers in een lijst staat: de kinderen van positie i zijn posities 2i + 1 en 2i + 2. In een max-heap is elke ouder minstens zo groot als zijn kinderen, dus de grootste waarde staat altijd in de wortel, positie 0.
Waarom gaat het bouwen van de heap snel?
De meeste waarden staan onderin de boom en kunnen maar een of twee niveaus zakken. Tel je het werk over alle niveaus op, dan kost het hele bouwen minder dan 2n vergelijkingen, niet n log n.
Is heapsort stabiel?
Nee. Door de wortel naar het eind te wisselen gaan waarden over grote afstanden, dus gelijke waarden kunnen van volgorde veranderen.
Worden mijn getallen ergens naartoe gestuurd?
Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor