Binárna halda

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

Definícia[upraviť | upraviť zdroj]

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 (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 \log _2 n (zaokrúhľuje sa vždy nadol na celé číslo).