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.
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