Nalezení a odstranění minima

Binární minimová halda

HeapFindMin()

  • Triviální
  • Vrať klíč kořene haldy
  • Složitost:

HeapExtractMin()

  • Odstranění minima
  1. Minimum (kořen) prohodím s koncem haldy (vznikne z něj list, z listu kořen)
  2. Pro nový kořen bublat dolů (prohození se synem s nižším klíčem - tedy aby o hladinu výš stále bylo nižší číslo)
  • Složitost:
    • Na každé hladině strávíme operací, procházených hladin je nejvýše logaritmicky mnoho

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