Haldy

Haldy

1. Typy

   • Binární halda
     • Popis
       • Kompletní binární strom - všechny úrovně kromě jsou plně obsazeny
     • Operace
       • Insert
         • Přidat na konec haldy
         • Swapovat s parentem dokud není platná podmínka
       • AccessMin
         • Vrátí kořen
       • Delete / DeleteMin
         • Prohoď prvek s posledním prvkem haldy
         • Swapuj dokud není obnovena podmínka haldy
         • Smaž poslední prvek
       • BuildHeap
         • Seřadí pole do haldy
         • Od dolní meze poloviny délky pole až po první prvek volá Heapify
           • Pokud jeden nebo více potomků je větší než rodič
           • Prohod většího z potomků s rodičem
         • O(n)
     • Reprezentace
       • Spojový seznam
       • Pole
         • X(1)- kořen
         • X(n) - prvek
         • X(2n) / X(2n+1) - potomci
   • Binomiální halda
     • Popis
       • Les binomiálních stromů odlišného stupně
       • Každý strom daného stupně může být přítomen max 1
       • Binomiální strom je definován rekurzivně
         • Stupeň 0 je jeden prvek
         • Stupeň k má kořen, jehož potomci jsou stromy stupňě k-1, k-2,...,1,0
       • Výška binomiálního stromu je rovna jeho stupni
       • Kořen binomiálního stromu má právě k potomků
       • Binomiální strom má právě 2^k prvků
       • i-tá úroveň binomiálního stromu obsahuje právě k nad i prvků
     • Reprezentace
       • Kořeny jsou v linked listu protože na kořeny se nedotazujeme náhodně
       • Udržujeme minpointer který odkazuje na strom s nejmenším kořenem
     • Operace
       • Insert
         • Vytvoří novou haldu s jedním stromem 0 stupně a zavolá merge na původní haldu
       • AccessMin
         • Vrátí kořen z minpointeru
       • Merge
         • Spojí dvě haldy do jedné
         • Spojí linkedlisty v pořadí podle stupně stromů
         • Zleva kontroluje stromy stejného stupně - 4 cases
           • k[x] <= k[x+1]
             • x+1 je potomek x
           • k[x] > k[x+1]
             • x je potomek x+1
           • k[x] != l[x+1]
             • Jdi dál
           • k[x] == k[x+1] == k[x+2]
             • Jdi dál
       • Delete
         • Přidej potomky min stromu jako nové bin. stromy nové haldy
         • Smaž původní min strom
         • Zavolej merge
       • DecreseKey
         • Stejné jako u binárního stromu
       • Delete
         • Klíč prvku je -INF
         • Stane se novým minimem
           • Zavolej delete min
   • Fibonacciho halda
     • Vlastnosti
       • Amortizovaná složitost lepší než bin. halda
       • Nevhodná pro real-time systémy protože některé operace mají lineární složistot
       • Složitá na implementaci
     • Operace
       • DeleteMin
         • Všechny potomky stromu nalinkovat na původní místo kořene
         • Consolidate
           • Začni od minima a postupuj doprava dokud neprojdeš všechny kořeny
           • Do pole A ukládej odkaz na strom na pozici d kde d je stupeň stromu
           • Jakmile narazíš na strom, který je stejného stupně jako už dříve objevený (A[d] je obsazeno)
             • Kořen s menším klíčem nalinkuj jako potomka většího klíče
             • Zvyš stupeň stromu a znovu prověř, jestli už nebyl takový strom nalezen
         • Náhodný kořen je nový min
       • Instert
         • Přidej nový strom s jedním prvkem
         • Nastav mark na false
       • DecreaseKey
         • Sniž hodnotu klíče
         • Pokud je menší než rodič, odřízni ho a přidej jako nový strom
           • Pokud rodič byl marked odřízni ho taky
       • Delete
         • DecreaseKey na nekonečno a deleteMin
     • Popis
       • Uvolněná varianta bin. haldy
       • Markuje uzly při odebrání potomka
         • Je-li odebrán potomek označenému uzlu, rodič je odtržen a přidán jako nový strom
         • Díky tomu je velikost podstromu stupně k alepsoń Fk+2 kde Fk je kté Fibb. číslo
       • Nepotřebné operace odkládá na později
         • Spojení stromů se dělá jen při DeleteMin (consolidate)
         • Amortizovaná složitost většiny operací je tak konstantní
     • Reprezentace
       • Obousměrný kruhový seznam sousedů a kořenů
       • Odkaz na prvního potomka
   • n-ární halda
     • Zobecnění binární haldy
     • Operace analogicky stejné
     • Asymptotická složitost operací stejná
     • Přesná složitost odlišná podle základu logaritmu
     • BInární halda je efektivní protože lze využívat binárních posunů pro průchod stromem
     • n-ární halda je rychlejší pro haldy, které se nevlezou do paměti počítače

2. Datová struktura (obvykle strom), která splňuje podmínku haldy

   • Pokud B je potomek A, pak key(B)>=key(A)

Imágenes y archivos del mapa