Řazení
Řazení haldou
 Vytisknout studijní materiál

Řazení haldou

V kapitole prioritní fronta jsme uvedli první verzi řazení využívajícího haldu, v níž jsme haldu nad polem řazených prvků vytvořili analogií s jejich postupným vkládáním, což vedlo k časové náročnosti vytvoření haldy n log2 n. Klasický algoritmus řazení haldou vytvoří haldu nad polem řazených prvků v lineárním čase.

Ze známých důvodů uvažujme, že řazené prvky jsou v poli a v prvcích a[1] a[pocet] . Musíme si uvědomit, že metoda dolu( ) vytvoří haldu, pro podstrom s kořenem v kterémkoliv prvku stromu, pokud levý a pravý podstrom jsou haldy. Protože listy stromu jsou jednoprvkové haldy, budeme-li metodou dolu( ) postupně vytvářet haldy od prvku a[pocet/2] až ke kořenu stromu a zespoda nahoru vytvoříme haldu nad původním polem.

Algoritmus řazení haldou potom je na obr.. Ukažme, že první cyklus vytvoří haldu. Jeho invariant je následující:

Na začátku každé iterace, všechny vrcholy s indexy i + 1, i + 2, ..., pocet jsou kořeny hald.

Inicializace: Před první iterací je i == pocet/2, tedy i je předchůdcem posledního listu. Jinými slovy, žádný z následujících vrcholů již nemá následníky, jsou tedy listy a tím kořeny jednoprvkových hald.

Udržování: Následníci vrcholu i mají indexy větší než i, jsou tedy haldami a metoda dolu( ) vytvoří haldu s kořenem i, přičemž zachová haldy s kořeny i + 1, i + 2, ..., pocet. Dekrementováním i obnovíme invariant před další iterací.

Skončení: Po skončení je i == 0, a tedy každý vrchol i = 1, 2, ..., pocet je kořenem haldy a specielně je ním vrchol s indexem 1.

Podobně jako při vytváření haldy postupným vkládáním je časová náročnost metody dolu( ) O(log2 n) a počet její volání je O(n), tedy časová náročnost vytvoření haldy je omezena O(n log2 n). To je pravda, ale je lepší omezení. Ukážeme si ho pro n = 2k - 1. Metoda dolu( ) bude volána 2k-2 krát na stromy o výšce 1, 2k-3 krát na stromy o výšce 2 atd. až jednou pro kořen stromu s výškou k - 1. Časová náročnost vytvoření haldy potom je

Důkaz pro n ≠ 2k - 1 je podobný.

Vzhledem na druhý cyklus na obr., kde je n - 1 krát volána metoda dolu( ), která je O(log2 n), je i čas výpočtu klasického algoritmu řazení haldou O(n log2 n).