Jämförelser
Byten
Uttagna

  • Sjunker ned
  • Jämförda
  • Bytta
  • På plats

Mer om heapsort

Heapsort

Heapsort (högsortering) läser listan som ett binärt träd och ordnar om den till en max-heap, där varje förälder är minst lika stor som sina barn. Det största värdet står då överst. Byt det till slutet, där det stannar, reparera heapen och upprepa. Appen ritar heapen som ett träd ovanför staplarna, så att du kan följa varje värde när det sjunker ned. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Trädet ovanför staplarna visar samma värden som en heap. Rutorna räknar jämförelser, byten och de värden som tagits ut ur heapen. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
  3. Följ trädet: först sjunker varje förälder ned tills heapen är byggd, sedan byts roten till slutet och heapen krymper med ett.

Så fungerar heapsort

Läs listan som ett träd: värdet på plats i har sina barn på platserna 2i + 1 och 2i + 2. Bygg en max-heap genom att låta varje förälder sjunka ned, med början i den sista föräldern: så länge ett värde är mindre än sitt största barn byter de två plats. När roten har det största värdet byter du det mot heapens sista värde. Det värdet är nu klart, heapen är ett kortare och den nya roten sjunker ned så att det blir en heap igen. Upprepa tills heapen är tom.

Alltid n log n, på plats

Trädet har ungefär log₂ n nivåer, så varje nedsjunkning tar högst ungefär 2 log₂ n jämförelser, och att bygga heapen tar färre än 2n. Det ger heapsort ett värsta fall på ungefär 2n log₂ n jämförelser, utan buffert: för 40 värden högst 352. Till skillnad från quicksort har den inga dåliga indata, och till skillnad från mergesort behöver den inget extra minne. I praktiken är den oftast långsammare än båda, eftersom den hoppar runt i listan, och den är inte stabil.

Ofta ställda frågor

Hur fungerar heapsort?

Den gör om listan till en max-heap, ett träd som lagras i listan där varje förälder är minst lika stor som sina barn. Sedan byter den gång på gång det största värdet, i roten, till slutet av heapen och låter den nya roten sjunka ned för att reparera heapen.

Vad är en heap?

Ett komplett binärt träd som lagras i en lista utan pekare: barnen till plats i är platserna 2i + 1 och 2i + 2. 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, plats 0.

Varför går det snabbt att bygga heapen?

De flesta värden ligger nära botten av trädet och kan bara sjunka en eller två nivåer. Summerar man arbetet över alla nivåer blir det färre än 2n jämförelser för hela bygget, inte n log n.

Är heapsort stabil?

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

Skickas mina tal någonstans?

Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

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

Gå till Editor