Heapsort

Heapsort är urvalssortering med ett bättre sätt att hitta det största värdet. Den håller de osorterade värdena i en heap, ett träd som lagras i själva listan, där det största värdet alltid står överst. Att ta ut det och reparera heapen tar ungefär log n steg i stället för en hel genomsökning.

En heap ritad som ett binärt träd ovanför samma värden som staplar, där det största värdet i roten byts till slutet av listan
En heap ritad som ett binärt träd ovanför samma värden som staplar, där det största värdet i roten byts till slutet av listan

Ett träd i en lista

En binär heap är ett träd som inte behöver några pekare. Plats 0 är roten, och barnen till plats i är platserna 2i + 1 och 2i + 2, så plats 1 och 2 är rotens barn, platserna 3 till 6 nästa nivå, och så vidare. Varje nivå är full utom den sista, som fylls från vänster. I en max-heap är varje förälder minst lika stor som sina barn, så det största värdet står alltid i roten.

Nedsjunkning

En enda operation gör allt arbete. För att låta ett värde sjunka ned jämför du det med dess barn. Om det största barnet är större än värdet byter de plats, och värdet jämförs med sina nya barn. Det stannar när inget barn är större, eller när det når botten. Eftersom trädet bara har ungefär log₂ n nivåer tar en nedsjunkning högst ungefär 2 log₂ n jämförelser.

Först heapen, sedan sorteringen

För att bygga heapen låter du varje förälder sjunka ned, från den sista tillbaka till roten. Varje delträd är en heap innan dess förälder sjunker ned i det. Sortera sedan: byt roten, det största värdet, mot heapens sista värde. Det värdet står nu på sin slutliga plats. Heapen är ett kortare, och värdet som hamnade i roten sjunker ned för att reparera den. Upprepa tills ett värde återstår.

Ett exempel

Ta 5, 1, 4, 2, 8. När heapen byggs sjunker 1 ned under 8, sedan 5 ned under 8, vilket ger 8, 5, 4, 2, 1. Nu byts 8 till slutet; 1 hamnar i roten och sjunker ned förbi 5 och 2: 5, 2, 4, 1 | 8. Sedan går 5 till slutet och 1 sjunker ned förbi 4: 4, 2, 1 | 5, 8. Två rundor till gör listan klar: 1, 2, 4, 5, 8, efter 12 jämförelser och 10 byten.

Styrkor och svagheter

Heapsort tar tid proportionell mot n log n även i värsta fall, och den behöver inget extra minne. Quicksort kan bli så långsam som n² och mergesort behöver en buffert lika lång som listan, så heapsort är den säkra reservlösningen: introsort, som används i C++ standardbibliotek, byter till den när quicksorts uppdelningar går snett. På riktiga datorer är den oftast långsammare än båda, eftersom den hoppar mellan avlägsna platser i listan, och den är inte stabil. J. W. J. Williams publicerade heapsort, tillsammans med den binära heapen, 1964.

Utforska den

Öppna appen och tryck på Steg. Trädet ovanför staplarna visar heapen: värdet som sjunker ned har en egen färg, barnet det jämförs med är markerat, och varje byte syns både i trädet och i staplarna. När heapen är byggd ser du roten bytas till slutet, bli grön och försvinna ur trädet.

Ofta ställda frågor

Vilken tidskomplexitet har heapsort?

O(n log n) i bästa, genomsnittliga och värsta fall. Att bygga heapen tar O(n), och vart och ett av de n − 1 uttagen tar O(log n). Den sorterar på plats med O(1) extra minne.

Vad är skillnaden mellan heapsort och urvalssortering?

Båda tar det största (eller minsta) återstående värdet gång på gång. Urvalssortering hittar det genom att söka igenom hela den osorterade delen, n jämförelser varje gång. Heapsort håller den osorterade delen i en heap, där det största värdet redan står överst, och att reparera heapen kostar bara ungefär log n jämförelser.

Vad används en heap till förutom sortering?

Prioritetsköer: en heap ger det största (eller minsta) elementet direkt och låter dig lägga till eller ta bort element på ungefär log n steg. Schemaläggare, Dijkstras algoritm för kortaste vägen och händelsesimuleringar använder alla en.

Är heapsort stabil?

Nej. När roten byts till slutet flyttas värden långa sträckor, så lika värden kan byta inbördes ordning.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova heapsort