Heapsort
Z Wikipedie, otevřené encyklopedie
Heapsort neboli řazení haldou je jeden z nejlepších obecných algoritmů řazení, založených na porovnávání prvků. Byť je v průměru o něco pomalejší než dobře napsaný quicksort, je jeho zaručená časová náročnost O(N log n) a dokáže třídit data na původním místě (má pouze konstantní nároky na paměť).
Obsah |
[editovat] Popis algoritmu
Základní myšlenkou tohoto kroku je využití datové struktury označované jako halda (angl. heap). Tato struktura umí velmi efektivně provést operaci vložení prvku a operaci výběr největšího prvku. Proto lze pomocí haldy setřídit dodaná data od největšího k nejmenšímu prostě pomocí jejich vložení do haldy a následného postupného vybírání největšího prvku.
V praxi lze haldu vystavět přímo ve vstupním poli tím způsobem, že jsou následovníci prvku n uloženi do prvků 2n a 2n+1 (při indexování od jedničky), a také následné vybírání prvků lze provádět pouhým přeuspořádáváním dat v tomto poli.
[editovat] Pomocný algoritmus
Pro oba kroky je využit pomocný algoritmus, který v čase O(log(n)) dokáže prodloužit haldu zpředu o jeden prvek. Přesněji řečeno - pokud všechny prvky s indexy L+1 až R (včetně krajních prvků) splňují pravidla haldy, po provedení pomocného algoritmu budou splňovat podmínky haldy prvky s indexy L až R. Je dobré si uvědomit, že prvky s indexy (N/2+1 až N) splňují pravidla haldy automaticky - není je s čím porovnávat.
[editovat] Stavba haldy
První krok haldového třídění spočívá v postupném prodlužování haldy z rozsahu (N/2 až N) na (1 až N). Po provedení N/2 kroků je halda vytvořena.
[editovat] Využití haldy
Halda, která splňuje popsané podmínky, má na vrcholu (index 1) prvek s největší hodnotou. Ve druhém kroku haldového třídění se tento prvek vymění za poslední prvek pole. Tak se na konec pole dostane největší prvek (tím je zatříděn na správné místo) ale prvkem, přesunutým z konce pole dojde k porušení pravidel haldy. Je třeba spustit pomocný algoritmus, tentokrát pro prvky s indexy (1 až N-1).
Výše zmíněný postup se opakuje pro stále se zmenšující haldu. Při každém kroku je na vrcholu haldy největší ze zbývajících prvků, a ten je výměnou s posledním prvkem této menší haldy zařazen na správné pořadí v poli.
