Binární minimová halda

  • Heap
  • Uchovává navzájem porovnatelné prvky - označujeme je klíče
  • Má tvar binárního stromu
  • Ve vrcholech uložena data (klíče)
  • Tvar:
    • Všechny hladiny kromě poslední musí mít plně obsazené
    • Poslední hladina musí být zaplněna od levého okraje k pravému (nemusí být plně zaplněná)
  • Haldové uspořádání:
    • Když pro každou dvojici otce a syna podívám na klíče, klíč otce musí být klíče syna

../Attachments/Pasted image 20221010093036.png

  • Globální minimum je nutně v kořeni

Počet hladin

  • Binární halda s prvky má hladin
Důkaz
  • Binární strom s úplnými hladinami má vrcholů
  • Vzhledem ke tvaru hladiny přibude nová hladina jen, když počet prvků vzroste z na
  • Funkce se právě při této změně zvětší o 1, tedy pro je počet hladin

Počet listů

  • Binární halda s má vnitřních vrcholů a listů

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25