Binárna halda

Binárna halda je jednoduchý typ stromovej dátovej štruktúry. Možno si ju predstaviť ako binárny strom s dvoma obmedzeniami.

Definícia

Nech K je úplne usporiadaná množina tzv. kľúčov (typicky množina čísel s prirodzeným usporiadaním). Binárna halda je binárny strom, ktorého uzly sú ohodnotené prvkami množiny K, a ktorý spĺňa tieto vlastnosti:

1. Dĺžka všetkých vetiev sa líši najviac o 1: majú dĺžku k, poprípade k-1. Číslu k sa potom označuje ako hĺbka haldy.
2. Hodnoty uzlov na každej vetve sú vzostupne (resp. zostupne) usporiadané.
   • Ak sú hodnoty uzlov na každej vetve zoradené vzostupne (čím ďalej od koreňa, tým väčšie hodnoty), je v koreni haldy najmenší prvok. Ide o tzv. minimovú haldu (min-heap).
   • Ak sú hodnoty uzlov na každej vetve zoradené zostupne (čím ďalej od koreňa, tým menšie hodnoty), je v koreni haldy najväčší prvok. Ide o tzv. maximovú haldu (max-heap).

Binárna halda sa dá výhodne reprezentovať postupnosťou hodnôt jej uzlov uložených v poli. Aby takáto reprezentácia bola jednoznačná, zavádza sa tzv. vľavo zarovnaná halda. Vľavo zarovnaná halda je binárna halda, ktorej všetky vetvy dĺžky k ležia naľavo od vetiev dĺžky k-1.

Veta: Vľavo zarovnaná binárna halda sa reprezentuje na n uzloch postupnosti hodnôt jej uzlov (a₁,..., a_n) takto:

• a₁ reprezentuje koreň haldy a ak je uzol u reprezentovaný prvkom a_i, potom ľavý nasledovník uzla u je reprezentovaný prvkom a_2i a pravý nasledovník uzla u je reprezentovaný prvkom a_2i+1. Potom postupnosť (a₁,..., a_n) je haldou určená jednoznačne.
• Veta umožňuje pracovať s vľavo zarovnanou binárnou haldou reprezentovanou v pamäti poľom. Vľavo zarovnaná binárna halda je to isté ako pole rozpísané "po vrstvách".

Neprázdna binárna halda na n uzloch má hĺbku $\log _{2}n$ (zaokrúhľuje sa vždy nadol na celé číslo).