Binomiální minimová halda

Funkce Složitost Popis
BHInsert Vloží do BH nový prvek
BHFindMin Vrátí minimum monžiny prvků BH
BHExtractMin Odstraní z BH minimum množiny jejích prvků
BHMerge Sloučí dvě BH do jední
BHBuild Postaví z prvků BH
BHDecreaseKey Sníží hodnotu klíče prvku BH
BHIncreaseKey Zvýší hodnotu klíče prvku BH
BHDelete Smaže prvek BH
  • BH obsahující prvků je uspořádaná množina binomiálních stromů , kde platí:
    • Stromy jsou v uspořádány vzestupně podle svých řádů
    • Pro každé nezáporné se v množině vyskytuje nejvýše jeden binomiální strom řádu
    • Každý vrchol v každém stromu obsahuje klíče
    • Pro každý strom platí haldové uspořádání klíčů

Paměťová reprezentace

  • Pro uložení uspořádané množiny stromů BH se používá spojový seznam
  • Vrchol může vypadat takto:
    • Pointer na otce
    • Hodnota
    • Pointer na levého sourozence
    • Pointer na nejpravějšího syna

Vlastnosti

  • Binomiální strom se vyskytuje v seznamu -prvkové BH právě tehdy, když v binárním zápisu čísla je

Operace

Nalezení minima - BHFindMin()

  • Globální minimum se nachází v jednom z kořenů stromů
  • Složitost: Stačí projet seznam , což bude trvat
  • Používáme-li tuto funkci často, vyplatí se udržovat pointer na globálně nejmenší kořen, pak je

Sloučení dvou BH - BHMerge()

  • Vytvoří jedinou BH, obsahující sjednocení prvků obou vstupních BH
  • Vyberu menší z kořenů a druhý stromeček zavěsím za něj (jako nejposlednějšího syna)
  • Podobné binárnímu sčítání pod sebou, přesun do vyššího řádu
  • Složitost:

Vložení - BHInsert()

  • Vytvoříme novou BH a pak sloučíme pomocí BHMerge() s původní BH
  • Složitost:
  • Amortizovaná složitost:

Odstranění minima - BHExtractMin()

  1. Najít strom s globálním minimem
  2. Odpojit z BH
  3. Odtrhnout jeho kořen
  4. Ze stromu vytvořit novou BH
  5. BHMerge()
  • Složitost

BHDecreaseKey()

  • Snížení hodnoty
  • BubbleUp

BHIncreaseKey()

  • BHDelete()
    • Snížení hodnoty prvku na co nejmenší (), takže vybublá nahoru
    • Extract prvku
  • Insert nového zvýšeného prvku (takže opět merge)

BHDelete()

  • Snížení hodnoty prvku na co nejmenší (), takže vybublá nahoru
  • Extract prvku

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