Heapsort

Heapsort er udvælgelsessortering med en bedre måde at finde den største værdi på. Den holder de usorterede værdier i en hob, et træ gemt i selve listen, hvor den største værdi altid står øverst. At tage den ud og reparere hoben tager omkring log n trin i stedet for en hel gennemgang.

En hob tegnet som et binært træ over de samme værdier som søjler, hvor den største værdi i roden byttes til enden af listen
En hob tegnet som et binært træ over de samme værdier som søjler, hvor den største værdi i roden byttes til enden af listen

Et træ inde i en liste

En binær hob er et træ, der ikke behøver pointere. Plads 0 er roden, og børnene til plads i er pladserne 2i + 1 og 2i + 2, så plads 1 og 2 er rodens børn, pladserne 3 til 6 det næste niveau og så videre. Hvert niveau er fuldt undtagen det sidste, som fyldes fra venstre. I en max-hob er hver forælder mindst lige så stor som sine børn, så den største værdi står altid i roden.

Nedsynkning

Én operation gør alt arbejdet. For at lade en værdi synke ned sammenligner du den med dens børn. Er det største barn større end værdien, bytter de, og værdien sammenlignes med sine nye børn. Det stopper, når intet barn er større, eller når værdien når bunden. Da træet kun har omkring log₂ n niveauer, tager en nedsynkning højst omkring 2 log₂ n sammenligninger.

Først hoben, så sorteringen

For at bygge hoben lader du hver forælder synke ned, fra den sidste tilbage til roden. Hvert deltræ er en hob, før dets forælder synker ned i det. Så sorterer du: byt roden, den største værdi, med hobens sidste værdi. Den værdi står nu på sin endelige plads. Hoben er én kortere, og den værdi, der landede i roden, synker ned for at reparere den. Gentag, til der er én værdi tilbage.

Et eksempel

Tag 5, 1, 4, 2, 8. Når hoben bygges, synker 1 ned under 8 og derefter 5 ned under 8, hvilket giver 8, 5, 4, 2, 1. Nu byttes 8 til enden; 1 lander i roden og synker ned forbi 5 og 2: 5, 2, 4, 1 | 8. Så går 5 til enden, og 1 synker ned forbi 4: 4, 2, 1 | 5, 8. To runder mere gør listen færdig: 1, 2, 4, 5, 8, efter 12 sammenligninger og 10 ombytninger.

Styrker og svagheder

Heapsort tager tid proportional med n log n selv i værste fald, og den kræver ingen ekstra hukommelse. Quicksort kan blive så langsom som n², og merge sort kræver en buffer så lang som listen, så heapsort er den sikre reserve: introsort, som C++' standardbibliotek bruger, skifter til den, når quicksorts opdelinger går galt. På rigtige computere er den som regel langsommere end begge, fordi den hopper mellem fjerne steder i listen, og den er ikke stabil. J. W. J. Williams offentliggjorde heapsort sammen med den binære hob i 1964.

Udforsk den

Åbn appen, og tryk på Trin. Træet over søjlerne viser hoben: værdien, der synker ned, har sin egen farve, barnet, den sammenlignes med, er fremhævet, og hver ombytning ses både i træet og i søjlerne. Når hoben er bygget, kan du se roden blive byttet til enden, blive grøn og forsvinde fra træet.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten for heapsort?

O(n log n) i bedste, gennemsnitlige og værste tilfælde. At bygge hoben tager O(n), og hver af de n − 1 udtagninger tager O(log n). Den sorterer in-place med O(1) ekstra hukommelse.

Hvad er forskellen på heapsort og udvælgelsessortering?

Begge tager den største (eller mindste) tilbageværende værdi igen og igen. Udvælgelsessortering finder den ved at gennemgå hele den usorterede del, n sammenligninger hver gang. Heapsort holder den usorterede del i en hob, hvor den største værdi allerede står øverst, og at reparere hoben koster kun omkring log n sammenligninger.

Hvad bruges en hob til ud over sortering?

Prioritetskøer: en hob giver det største (eller mindste) element med det samme og lader dig tilføje eller fjerne elementer i omkring log n trin. Planlæggere, Dijkstras korteste-vej-algoritme og hændelsessimuleringer bruger alle en.

Er heapsort stabil?

Nej. Når roden byttes til enden, flyttes værdier over lange afstande, så ens værdier kan skifte deres rækkefølge.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv heapsort