Heapsort

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 řadit data na původním místě (má pouze konstantní nároky na paměť).

[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 seřadit 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 řazení 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 řazení se tento prvek vymění za poslední prvek pole. Tak se na konec pole dostane největší prvek (tím je zařazen 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.

Tento článek o algoritmu nebo datové struktuře je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.