Haldy

Haldy

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

Media attachments

62e437f5-0ad2-4da7-a0e0-457307825337 (image/png)

Next up

Description

Resource summary

Media attachments

Similar

	Created by Michal Roch about 8 years ago