Haldy

Michal Roch
Mind Map by Michal Roch, updated more than 1 year ago
Michal Roch
Created by Michal Roch about 4 years ago
33
0

Description

PAL
Tags

Resource summary

Haldy
1 Typy
1.1 Binární halda
1.1.1 Popis
1.1.1.1 Kompletní binární strom - všechny úrovně kromě jsou plně obsazeny
1.1.2 Operace
1.1.2.1 Insert
1.1.2.1.1 Přidat na konec haldy
1.1.2.1.2 Swapovat s parentem dokud není platná podmínka
1.1.2.2 AccessMin
1.1.2.2.1 Vrátí kořen
1.1.2.3 Delete / DeleteMin
1.1.2.3.1 Prohoď prvek s posledním prvkem haldy
1.1.2.3.2 Swapuj dokud není obnovena podmínka haldy
1.1.2.3.3 Smaž poslední prvek
1.1.2.4 BuildHeap
1.1.2.4.1 Seřadí pole do haldy
1.1.2.4.2 Od dolní meze poloviny délky pole až po první prvek volá Heapify
1.1.2.4.2.1 Pokud jeden nebo více potomků je větší než rodič
1.1.2.4.2.2 Prohod většího z potomků s rodičem
1.1.2.4.3 O(n)
1.1.3 Reprezentace
1.1.3.1 Spojový seznam
1.1.3.2 Pole
1.1.3.2.1 X(1)- kořen
1.1.3.2.2 X(n) - prvek
1.1.3.2.3 X(2n) / X(2n+1) - potomci
1.2 Binomiální halda
1.2.1 Popis
1.2.1.1 Les binomiálních stromů odlišného stupně
1.2.1.2 Každý strom daného stupně může být přítomen max 1
1.2.1.3 Binomiální strom je definován rekurzivně
1.2.1.3.1 Stupeň 0 je jeden prvek
1.2.1.3.2 Stupeň k má kořen, jehož potomci jsou stromy stupňě k-1, k-2,...,1,0
1.2.1.4 Výška binomiálního stromu je rovna jeho stupni
1.2.1.5 Kořen binomiálního stromu má právě k potomků
1.2.1.6 Binomiální strom má právě 2^k prvků
1.2.1.7 i-tá úroveň binomiálního stromu obsahuje právě k nad i prvků
1.2.2 Reprezentace
1.2.2.1 Kořeny jsou v linked listu protože na kořeny se nedotazujeme náhodně
1.2.2.2 Udržujeme minpointer který odkazuje na strom s nejmenším kořenem
1.2.3 Operace
1.2.3.1 Insert
1.2.3.1.1 Vytvoří novou haldu s jedním stromem 0 stupně a zavolá merge na původní haldu
1.2.3.2 AccessMin
1.2.3.2.1 Vrátí kořen z minpointeru
1.2.3.3 Merge
1.2.3.3.1 Spojí dvě haldy do jedné
1.2.3.3.2 Spojí linkedlisty v pořadí podle stupně stromů
1.2.3.3.3 Zleva kontroluje stromy stejného stupně - 4 cases
1.2.3.3.3.1 k[x] <= k[x+1]
1.2.3.3.3.1.1 x+1 je potomek x
1.2.3.3.3.2 k[x] > k[x+1]
1.2.3.3.3.2.1 x je potomek x+1
1.2.3.3.3.3 k[x] != l[x+1]
1.2.3.3.3.3.1 Jdi dál
1.2.3.3.3.4 k[x] == k[x+1] == k[x+2]
1.2.3.3.3.4.1 Jdi dál
1.2.3.4 Delete
1.2.3.4.1 Přidej potomky min stromu jako nové bin. stromy nové haldy
1.2.3.4.2 Smaž původní min strom
1.2.3.4.3 Zavolej merge
1.2.3.5 DecreseKey
1.2.3.5.1 Stejné jako u binárního stromu
1.2.3.6 Delete
1.2.3.6.1 Klíč prvku je -INF
1.2.3.6.2 Stane se novým minimem
1.2.3.6.2.1 Zavolej delete min
1.3 Fibonacciho halda
1.3.1 Vlastnosti
1.3.1.1 Amortizovaná složitost lepší než bin. halda
1.3.1.2 Nevhodná pro real-time systémy protože některé operace mají lineární složistot
1.3.1.3 Složitá na implementaci
1.3.2 Operace
1.3.2.1 DeleteMin
1.3.2.1.1 Všechny potomky stromu nalinkovat na původní místo kořene
1.3.2.1.2 Consolidate
1.3.2.1.2.1 Začni od minima a postupuj doprava dokud neprojdeš všechny kořeny
1.3.2.1.2.2 Do pole A ukládej odkaz na strom na pozici d kde d je stupeň stromu
1.3.2.1.2.3 Jakmile narazíš na strom, který je stejného stupně jako už dříve objevený (A[d] je obsazeno)
1.3.2.1.2.3.1 Kořen s menším klíčem nalinkuj jako potomka většího klíče
1.3.2.1.2.3.2 Zvyš stupeň stromu a znovu prověř, jestli už nebyl takový strom nalezen
1.3.2.1.3 Náhodný kořen je nový min
1.3.2.2 Instert
1.3.2.2.1 Přidej nový strom s jedním prvkem
1.3.2.2.2 Nastav mark na false
1.3.2.3 DecreaseKey
1.3.2.3.1 Sniž hodnotu klíče
1.3.2.3.2 Pokud je menší než rodič, odřízni ho a přidej jako nový strom
1.3.2.3.2.1 Pokud rodič byl marked odřízni ho taky
1.3.2.4 Delete
1.3.2.4.1 DecreaseKey na nekonečno a deleteMin
1.3.3 Popis
1.3.3.1 Uvolněná varianta bin. haldy
1.3.3.2 Markuje uzly při odebrání potomka
1.3.3.2.1 Je-li odebrán potomek označenému uzlu, rodič je odtržen a přidán jako nový strom
1.3.3.2.2 Díky tomu je velikost podstromu stupně k alepsoń Fk+2 kde Fk je kté Fibb. číslo
1.3.3.3 Nepotřebné operace odkládá na později
1.3.3.3.1 Spojení stromů se dělá jen při DeleteMin (consolidate)
1.3.3.3.2 Amortizovaná složitost většiny operací je tak konstantní
1.3.4 Reprezentace
1.3.4.1 Obousměrný kruhový seznam sousedů a kořenů
1.3.4.2 Odkaz na prvního potomka
1.4 n-ární halda
1.4.1 Zobecnění binární haldy
1.4.2 Operace analogicky stejné
1.4.3 Asymptotická složitost operací stejná
1.4.4 Přesná složitost odlišná podle základu logaritmu
1.4.5 BInární halda je efektivní protože lze využívat binárních posunů pro průchod stromem
1.4.6 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
2.1 Pokud B je potomek A, pak key(B)>=key(A)
Show full summary Hide full summary

Similar

Computing
Kwame Oteng-Adusei
Pythagorean Theorem Quiz
Selam H
A level Computing Quiz
Zacchaeus Snape
Geometry Vocabulary
patticlj
Algebra 2 Quality Core
Niat Habtemariam
Types and Components of Computer Systems
Jess Peason
Input Devices
Jess Peason
Project Communications Management
farzanajeffri
Output Devices
Jess Peason
Common Technology Terms
Julio Aldine Branch-HCPL
Abstraction
Shannon Anderson-Rush