Řazení haldou

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Heapsort v akci na několika náhodných číslech. Před samotným řazením je nastíněna stromová struktura.
Ukázka práce algoritmu s využitím haldy.

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ěť). Heapsort není stabilní řadící algoritmus.

Popis algoritmu[editovat | editovat zdroj]

Základní myšlenkou tohoto algoritmu 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.

Algoritmus funguje s libovolnou implementací haldy. Při řazení prvků v poli lze využít následující implementaci haldy v poli, která dovoluje třídit prvky na místě.

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.

Pomocný algoritmus[editovat | editovat zdroj]

Uvažujme binární haldu pro nalezení "nejvyššího" prvku. Tato halda bude umístěna v poli od indexu 1 do indexu N. "Pravidlem haldy" je, že prvek umístěný na indexu i je vyšší než prvky umístěné na indexu 2*i a 2*i+1. U koncových uzlů na indexech (N/2+1 až N) je "pravidlo haldy" automaticky splněné - není je s čím porovnávat.

Pro oba kroky řazení je využit pomocný algoritmus, který v čase O(log(n)) dokáže prodloužit částečně vytvořenou haldu zepř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í "pravidlo haldy", po provedení pomocného algoritmu budou splňovat pravidlo haldy prvky s indexy L až R. Pokud prvek na indexu L nevyhovuje pravidlu haldy, vyměníme ho s větším z prvků na indexech 2*L a 2*L+1 a postup zopakujeme pro index s kterým jsme měnili.

Stavba haldy[editovat | editovat zdroj]

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.

Využití haldy[editovat | editovat zdroj]

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 pro zatřídění vyměněného prvku na indexu 1 do haldy, aby tentokrát vznikla halda 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.