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: 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. 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 (a1,..., an) takto: a1 reprezentuje koreň haldy a ak je uzol u reprezentovaný prvkom ai, potom ľavý nasledovník uzla u je reprezentovaný prvkom a2i a pravý nasledovník uzla u je reprezentovaný prvkom a2i+1. Potom postupnosť (a1,..., an) 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 (zaokrúhľuje sa vždy nadol na celé číslo).
Iné projekty
Kategória:Haldy