Skip to main content.

Zaradenie a popis

Heapsort (triedenie haldou) je triediaci algoritmus, ktorý triedi prvky postupnosti použitím špeciálnej dynamickej dátovej štruktúry halda. Je to jeden z najlepších všeobecných algoritmov triedenia založených na porovnávaní prvkov a je efektívnou verziou Selection Sortu. Hoci je v priemernom prípade o niečo pomalší ako quicksort, jeho najhoršia časová zložitosť je len O(n log n).

^ TOP

Motivácia a špecifikácia

Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať túto postupnosť vzostupne v najhoršom čase O(n log n).
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A

^ TOP

Myšlienka algoritmu

Triedenie prebieha v dvoch fázach: vytvorenie haldy a výpis haldy v utriedenom poradí.
Algoritmus teda najprv vytvorí zo vstupného poľa haldu použitím procedúry Build-heap.
Najväčší prvok v halde je uložený na prvej pozícii poľa. Presunieme ho teda na jeho správne miesto (na koniec poľa – výmenou za prvok, ktorý sa tam nachádza). Teraz máme haldu menšiu o jeden prvok a v koreni je prvok, ktorý porušuje vlastnosť haldy. Zavolá sa procedúra Heapify, ktorá obnoví vlastnosť haldy a zas je na prvej pozícii poľa najväčší prvok. Toto sa opakuje až po haldu veľkosti 2.

^ TOP

Vizualizácia

Heapsort - animácia

^ TOP

Zápis algoritmu

Pre informácie o použitých procedúrach Build-Heap a Heapify pozri dátovú štruktúru halda. 

    Heapsort(A)
    Build-Heap(A)
    for i := length[A] downto 2 do
      exchange (A[1],A[i])
      heap-size[A] := heap-size[A]-1
      Heapify(A,1)
^ TOP

Vlastnosti algoritmu

Čas behu algoritmu je O(n log n), keďže vytvorenie haldy trvá O(n) a každé z n-1 volaní udržiavania haldy (heapify) trvá O(n log n).
Paradoxne dostávame najlepší čas behu algoritmu práve keď je vstupná postupnosť už čiastočne utriedená v opačnom poradí. Vtedy totiž fáza vytvárania haldy nevyžaduje žiadne presuny Heapsort nie je stabilné triedenie. Má len konštantné nároky na pamäť, teda triedi prvky in-situ.

^ TOP

Experimentovanie

University of Hawaii System, Hawaii
Applet na testovanie heapsortu.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

School of Computing and Information Sciences, Florida International University, USA
Prehľadný java applet na experimentáciu so Shell sortom.
http://www2.hawaii.edu/~copley/665/HSApplet.html

^ TOP