Halda

Strom má vlastnost haldy, když klíč v každém vrcholu je větší nebo roven klíčům v jeho následnících, pokud je má. Ekvivalentně, klíč v každém vrcholu je menší nebo roven klíči v jeho předchůdci, pokud ho má. Z uvedené vlastnosti plyne, že žádný vrchol ve stromě s vlastností haldy nemá klíč větší než kořen.

Halda je úplný binární strom s vlastností haldy reprezentován pomocí pole.

Příklad haldy je na obr. .

Připomeňme, že binární strom je polem implementován tak, že je-li kořen prvek pole s indexem 1, následníci prvku s indexem k jsou prvky 2k a 2k + 1 a předchůdce prvku k je k/2.

Uvedená vlastnost a binární strom s touto vlastností se přesněji nazývá max-halda. Obdobně se zavádí vlastnost min-halda a binární úplný strom s touto vlastností stejného jména. Pokud nic neřekneme, pod haldou budeme rozumět max-haldu.

Máme-li prioritní frontu implementovanou haldou, potom nalezení největšího prvku je O(1). Jeho výběr však vyžaduje náhradu prvku, který byl kořenem. Aby jsme zachovali požadavek úplného stromu, nahradíme ho posledním prvkem nejnižší úrovně, což může vést k porušení vlastnosti hlady, pokud by tento prvek měl menší klíč, než některý z jeho následníků. Na druhé straně, vložíme-li prvek, bude tento dalším listem a pokud má větší klíč než jeho předchůdce, opět došlo k porušení vlastnosti haldy. Uvedené situace můžeme zobecnit na dva případy kdy se poruší vlastnost haldy a nutno ji obnovit, chceme-li využívat její vlastnost.

V prvním případě je vlastnost haldy porušena, protože klíč vrcholu se stane menším než klíč v jednom nebo obou následnících. V tomto případě ho musíme vyměnit s větším z jeho následníku, což může vést k porušení vlastnosti o úroveň níže a postup výměny opakujeme. Tímto postupem prvek, který takto porušil vlastnost haldy putuje směrem dolů, k listům. Jeho postup skončí, když bude splněna vlastnost haldy anebo se stane listem. Uvedený postup je ilustrovám na obr. .

Obnovení vlastnosti haldy s celými čísly o velikosti pocet, reprezentované prvky pole pf[1] až pf[pocet], v níž se stal pf[k] menším než jeden nebo oba jeho následníci potom implementuje metoda dolu( ) na obr.. Cyklus v této metodě skončí, sestoupíme-li k listu, tj. index potenciálního levého následníka je větší než počet uložených prvků anebo příkazem break, obnoví-li se vlastnost haldy dříve. Proměnná j je index levého následníka vrcholu k a je-li j == pocet, potom vrchol s indexem pocet/2 má jenom jednoho a to levého následníka. V opačném případě se vybere větší z následníků vrcholu k a zjišťuje se, je-li splněna vlastnost haldy. Metoda vymen( ) vymění prvky v poli pf s indexy k a j.

Ve druhém případě je vlastnost haldy porušena, když klíč ve vrcholu se stane větším než klíč v jeho předchůdci. Pro obnovení vlastnosti haldy ho musíme vyměnit s jeho předchůdcem, což v tomto případě může vést k porušení vlastnosti haldy o úroveň výše a postup opakujeme. Tímto způsobem prvek, který porušil vlastnost haldy putuje směrem nahoru, ke kořenu. Skončíme, když se obnoví vlastnost haldy anebo se stane kořenem. Uvedený postup je ilustrován na obr. a implementuje metoda nahoru( ) na obr..

Prioritní frontu nyní můžeme implementovat pomocí haldy (obr.). Operace vlož nejprve vloží prvek na konec pole pf, zvětší počet uložených prvků o 1 a pomocí metody nahoru( ) obnoví vlastnost haldy pokud byla porušena. Operace výběru největšího prvku, vymění první a poslední prvek pole pf, metodou dolu( ) obnoví, pokud nutno, haldu s počtem prvků o 1 menším a vrátí hodnotu prvku s indexem pocet, což je původní prvek s indexem 1, tedy kořen a pocet sníží o 1.

Nyní délka cesty prvku při obnovení vlastnosti haldy v metodách vloz( ) a vybermax( ) je nejvíce log₂ n, kde n je počet prvků v prioritní frontě. Operace vlož pro prioritní frontu při použití haldy tedy potřebuje nejvíce log₂ n porovnání a operace výběru největšího prvku nejvíce 2log₂ n porovnání.

Konstantní faktor pro počet přiřazení při vkládání prvku porušujícího vlastnost haldy na správné místo metodami nahoru( ) a dolu( ), lze zlepšit stejnou technikou jakou jsme požili v programu pro řazení vkládáním pro vložení prvku do seřazené předcházející posloupnosti.

Vytvoření haldy s n prvky postupným vkládáním prvků operací vlož v nejhorším případě, kdy každý vložený prvek musí projít cestu až k vrcholu potom trvá čas menší než n log₂ n, protože

log₂ n + ... + log₂ 2 + log₂ 1 < n log₂ n