Phenquestions
Ilustrácia haldy dátových štruktúr
Existujú dva typy háld: hromada max a hromada min. V štruktúre max-heap je maximálna hodnota koreň a pri zostupovaní stromu sa hodnoty zmenšujú; každý rodič má rovnakú alebo väčšiu hodnotu ako ktorékoľvek z jeho bezprostredných detí. Štruktúra haldy min je tam, kde minimálna hodnota je koreň a hodnoty sa zväčšujú pri klesaní stromu; akýkoľvek rodič má rovnakú alebo menšiu hodnotu ako ktorékoľvek z jeho bezprostredných detí. V nasledujúcich diagramoch je prvá hromada max a druhá hromada min:
Pri obidvoch hromadách si všimnite, že pre pár detí nezáleží na tom, či má tá vľavo väčšiu hodnotu. Riadok v úrovni stromu nemusí byť nevyhnutne vyplnený od minima po maximum zľava; nie je tiež nevyhnutne vyplnená z maxima na minimum zľava.
Zastupovanie haldy v poli
Aby softvér mohol haldu ľahko použiť, musí byť halda zastúpená v poli. Maximálna halda uvedená vyššie v poli je:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Toto sa začína s koreňovou hodnotou ako prvou hodnotou pre pole. Hodnoty sa nepretržite umiestňujú čítaním stromu zľava doprava, zhora nadol. Ak prvok chýba, jeho poloha v poli sa preskočí. Každý uzol má dve deti. Ak je uzol na indexe (pozícia) n, jeho prvé dieťa v poli je na indexe 2n + 1 a jeho ďalšie dieťa je na indexe 2n + 2. 89 je v indexe 0; jeho prvé dieťa, 85 je na indexe 2 (0) + 1 = 1, zatiaľ čo jeho druhé dieťa je na indexe 2 (0) + 2 = 2. 85 je v indexe 1; jeho prvé dieťa, 84, je na indexe 2 (1) + 1 = 3, zatiaľ čo jeho druhé dieťa, 82, je na indexe 2 (1) + 2 = 4. 79 je v indexe 5; jeho prvé dieťa, 65 je na indexe 2 (5) + 1 = 11, zatiaľ čo jeho druhé dieťa je na indexe 2 (5) + 2 = 12. Vzorce sa použijú na zvyšok prvkov v poli.
Takéto pole, kde význam prvku a vzťah medzi prvkami vyplýva z polohy prvku, sa nazýva implicitná dátová štruktúra.
Implicitná dátová štruktúra pre vyššie uvedenú min haldu je:
65, 68, 70, 73, 71, 83, 84,,, 79, 80,, 85, 89Vyššie uvedená halda je úplný binárny strom, ale nie úplný binárny strom. Preto sú niektoré miesta (pozície) v poli prázdne. V prípade úplného binárneho stromu nebude v poli prázdne žiadne miesto.
Teraz, ak by halda bola takmer úplným stromom, napríklad keby chýbala hodnota 82, pole by bolo:
89, 85, 87, 84, 79, 73, 80, 81,,, 65, 69V tejto situácii sú tri miesta prázdne. Vzorce sú však stále použiteľné.
Operácie
Dátová štruktúra je formát údajov (napr.g. strom), plus vzťah medzi hodnotami plus operácie (funkcie), ktoré sa s hodnotami vykonávajú. Pre hromadu je vzťah, ktorý prechádza celou hromadou, že rodič musí mať rovnakú alebo vyššiu hodnotu ako deti, pre maximálnu hromadu; a rodič musí mať rovnakú alebo menšiu hodnotu ako deti pre minimálnu hromadu. Tento vzťah sa nazýva vlastnosť haldy. Činnosti haldy sú zoskupené pod hlavičkami Tvorba, Základné, Vnútorné a Inšpekcia. Nasleduje súhrn činností haldy:
Zhrnutie operácií haldy
S hromadami existujú spoločné určité softvérové operácie:
Vytvorenie haldy
create_heap: Vytvorenie haldy znamená vytvorenie objektu, ktorý predstavuje haldu. V jazyku C môžete vytvoriť haldu s typom objektu struct. Jedným z členov štruktúry bude halda pole. Zvyšok členov budú funkcie (operácie) pre haldu. Create_heap znamená vytvorenie prázdnej haldy.
Heapify: Haldové pole je čiastočne zoradené (zoradené) pole. Heapify znamená, poskytnúť haldy pole z netriedeného poľa - pozri podrobnosti nižšie.
Zlúčiť: To znamená, vytvoriť hromadu zväzkov z dvoch rôznych háld - podrobnosti nájdete nižšie. Dve hromady by mali byť obidve hromady max. Alebo min. Nová halda je v súlade s vlastnosťou haldy, zatiaľ čo pôvodné haldy sú zachované (nevymazané).
Meld: To znamená, spojiť dve hromady rovnakého typu a vytvoriť novú. Zachovajú sa duplikáty - podrobnosti nájdete nižšie. Nová halda je v súlade s vlastnosťou haldy, zatiaľ čo pôvodné haldy sú zničené (vymazané). Hlavný rozdiel medzi zlúčením a splynutím je v tom, že pri spájaní sa jeden strom hodí ako podstrom ku koreňu druhého stromu, čo umožňuje duplicitné hodnoty v novom strome, zatiaľ čo pri zlúčení sa vytvorí nový haldy, ktorý odstráni duplikáty. Nie je potrebné udržiavať dve pôvodné haldy tavením.
Základné haldy
find_max (find_min): Nájdite maximálnu hodnotu v poli max-heap a vráťte kópiu alebo vyhľadajte minimálnu hodnotu v poli min-heap a vráťte kópiu.
Vložiť: Pridajte do prvku haldy nový prvok a usporiadajte pole tak, aby sa zachovala vlastnosť haldy v diagrame.
extract_max (extract_min): Nájdite maximálnu hodnotu v poli max-heap, odstráňte ju a vráťte späť; alebo vyhľadajte minimálnu hodnotu v poli min-heap, odstráňte ju a vráťte ju.
delete_max (delete_min): Nájdite koreňový uzol max-heap, ktorý je prvým prvkom poľa max-heap, odstráňte ho bez nutnosti jeho návratu; alebo vyhľadajte koreňový uzol min-haldy, ktorý je prvým prvkom poľa min-haldy, odstráňte ho bez toho, aby ste ho nevyhnutne vrátili;
Nahradiť: Nájdite koreňový uzol ktorejkoľvek haldy, odstráňte ho a nahraďte ho novým. Nezáleží na tom, či sa vráti starý koreň.
Operácie vnútornej haldy
increase_key (pokles_kľúč): Zvýšte hodnotu ľubovoľného uzla pre maximálnu haldu a preskupte ju tak, aby sa zachovala vlastnosť haldy, alebo znížte hodnotu ľubovoľného uzla pre minimálnu haldu a preskupte ju tak, aby sa zachovala vlastnosť haldy.
Odstrániť: odstránenie ľubovoľného uzla a následné usporiadanie, aby sa zachovala vlastnosť haldy pre maximálnu a minimálnu hromadu.
shift_up: presunúť uzol hore na maximálnu alebo minimálnu hromadu tak dlho, ako je potrebné, preskupením, aby sa zachovala vlastnosť haldy.
shift_down: presunúť uzol nadol v maximálnej alebo minimálnej halde tak dlho, ako je potrebné, preskupením, aby sa zachovala vlastnosť haldy.
Inšpekcia haldy
Veľkosť: Týmto sa vráti počet kľúčov (hodnôt) v halde; nezahŕňa prázdne miesta haldy poľa. Hromadu je možné znázorniť kódom, ako je to v diagrame, alebo poľom.
je prázdny: Toto vráti logickú hodnotu true, ak v halde nie je žiadny uzol, alebo logickú hodnotu false, ak má halda aspoň jeden uzol.
Preosievanie na hromadu
Existuje preosievanie a preosievanie dole:
Sift-Up: To znamená zameniť uzol za nadradeného. Ak vlastnosť haldy nie je uspokojená, vymeňte nadradeného objektu za svojho vlastného nadradeného. Takto pokračujte v ceste, kým nie je vlastnosť haldy spokojná. Postup môže dosiahnuť koreň.
Sift-Down: To znamená zameniť uzol veľkej hodnoty s menším z jeho dvoch detí (alebo jedným dieťaťom za takmer úplnú hromadu). Ak vlastnosť haldy nie je uspokojená, vymeňte dolný uzol za menší uzol svojich dvoch vlastných potomkov. Takto pokračujte v ceste, kým nie je vlastnosť haldy spokojná. Postup môže dosiahnuť list.
Heapifying
Heapify znamená triedenie nevytrieďeného poľa, aby bola vlastnosť heap uspokojená pre max-heap alebo min-heap. To znamená, že v novom poli môžu byť nejaké prázdne miesta. Základný algoritmus na heapifikáciu max-haldy alebo min-haldy je nasledovný:
- ak je koreňový uzol extrémnejší ako ktorýkoľvek z jeho detských uzlov, potom vymieňajte koreňový uzol s menej extrémnym detským uzlom.
- Opakujte tento krok s podradenými uzlami v schéme prechodu na strom predobjednávok.
Konečný strom je halda, ktorá vyhovuje vlastnosti haldy. Hromadu je možné znázorniť ako stromový diagram alebo ako pole. Výslednou hromadou je čiastočne triedený strom, t.j.e. čiastočne zoradené pole.
Podrobnosti operácie haldy
Táto časť článku poskytuje podrobnosti o halde.
Vytvorenie hromady podrobností
create_heap
Viď vyššie!
heapify
Viď vyššie
zlúčiť
Ak halda polia,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69a
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71sú zlúčené, výsledok bez duplikátov môže byť,
89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71Po nejakom preosievaní. Všimnite si, že v prvom poli 82 nemá žiadne deti. Vo výslednom poli je na indexe 4; a jeho polohy v indexe 2 (4) + 1 = 9 a 2 (4) + 2 = 10 sú voľné. To znamená, že v novom stromovom diagrame tiež nemá deti. Pôvodné dve hromady by sa nemali odstraňovať, pretože ich informácie nie sú v skutočnosti v novej kope (nové pole). Základný algoritmus na zlúčenie háld rovnakého typu je nasledovný:
- Pripojte jedno pole k spodnej časti druhého poľa.
- Heapify vylučuje duplikáty a zaisťuje, aby uzly, ktoré nemali deti v pôvodných hromadách, stále nemali deti v novej halde.
splynúť
Algoritmus na spájanie dvoch háld rovnakého typu (buď dvoch max- alebo dvoch min-) je nasledovný:
- Porovnajte dva koreňové uzly.
- Vytvorte menej extrémny koreň a zvyšok jeho stromu (podstrom), druhé dieťa extrémneho koreňa.
- Presuňte zatúlané dieťa od koreňa teraz extrémneho podstromu, smerom nadol v extrémnom podstrome.
Výsledná halda je stále v súlade s vlastnosťou haldy, zatiaľ čo pôvodné haldy sú zničené (vymazané). Pôvodné hromady môžu byť zničené, pretože všetky informácie, ktoré majú, sa stále nachádzajú v novej kope.
Základné haldy
find_max (find_min)
To znamená vyhľadať maximálnu hodnotu v poli max-heap a vrátiť kópiu alebo vyhľadať minimálnu hodnotu v poli min-heap a vrátiť kópiu. Haldové pole podľa definície už spĺňa vlastnosť haldy. Stačí teda vrátiť kópiu prvého prvku poľa.
vložiť
To znamená pridať nový prvok do haldy poľa a zmeniť usporiadanie poľa tak, aby bola zachovaná halda vlastnosti diagramu (spokojná). Algoritmus, ako to urobiť pre oba typy háld, je nasledovný:
- Predpokladajme plný binárny strom. To znamená, že pole musí byť na konci v prípade potreby vyplnené prázdnymi miestami. Celkový počet uzlov celej hromady je 1 alebo 3 alebo 7 alebo 15 alebo 31 atď.; pokračujte v zdvojnásobovaní a pridávaní 1.
- Umiestnite uzol na najvhodnejšie prázdne miesto o veľkosť, na koniec haldy (na koniec haldy). Ak nie je prázdne miesto, začnite nový riadok zľava dole.
- Ak je to potrebné, prepracujte, kým nie je vlastnosť haldy spokojná.
extract_max (extract_min)
Nájdite maximálnu hodnotu v poli max-heap, odstráňte ju a vráťte ju; alebo vyhľadajte minimálnu hodnotu v poli min-heap, odstráňte ju a vráťte ju. Algoritmus na extrakciu_max (extrakt_min) je nasledovný:
- Odstráňte koreňový uzol.
- Vezmite (odstráňte) najspodnejší pravý uzol (posledný uzol v poli) a umiestnite ku koreňu.
- Podľa potreby prepadnite, kým nie je vlastnosť haldy spokojná.
delete_max (delete_min)
Vyhľadajte koreňový uzol max-heap, ktorý je prvým prvkom poľa max-heap, odstráňte ho bez nutnosti jeho vrátenia; alebo vyhľadajte koreňový uzol minimálnej haldy, ktorý je prvým prvkom poľa minimálnej haldy, odstráňte ju bez nutnosti jej návratu. Algoritmus na odstránenie koreňového uzla je nasledovný:
- Odstráňte koreňový uzol.
- Vezmite (odstráňte) najspodnejší pravý uzol (posledný uzol v poli) a umiestnite ku koreňu.
- Podľa potreby prepadnite, kým nie je vlastnosť haldy spokojná.
vymeniť
Vyhľadajte koreňový uzol ktorejkoľvek haldy, odstráňte ho a nahraďte ho novým. Nezáleží na tom, či sa vráti starý koreň. Ak je to vhodné, prepadnite, kým nie je vlastnosť haldy spokojná.
Operácie vnútornej haldy
zvýšiť_kľúč (znížiť_kľúč)
Zvýšte hodnotu ľubovoľného uzla pre maximálnu haldu a preskupte ju tak, aby sa zachovala vlastnosť haldy, alebo znížte hodnotu ľubovoľného uzla pre minimálnu haldu a usporiadajte ju tak, aby sa zachovala vlastnosť haldy. Podľa potreby posúvajte nahor alebo nadol, kým nie je vlastnosť haldy spokojná.
vymazať
Odstráňte uzol, ktorý vás zaujíma, a potom znova usporiadajte, aby sa zachovala vlastnosť haldy pre maximálnu alebo minimálnu hromadu. Algoritmus na odstránenie uzla je nasledovný:
- Odstráňte uzol záujmu.
- Vezmite (odstráňte) najspodnejší pravý uzol (posledný uzol v poli) a umiestnite ho do indexu odstráneného uzla. Ak je odstránený uzol v poslednom riadku, nemusí to byť potrebné.
- Podľa potreby posúvajte nahor alebo nadol, kým nie je vlastnosť haldy spokojná.
posunúť hore
Presuňte uzol nahor na maximálnu alebo minimálnu hromadu tak dlho, ako je potrebné, preskupením, aby sa zachovala vlastnosť haldy - preosiať.
shift_down
Presuňte uzol nadol v maximálnej alebo minimálnej halde tak dlho, ako je potrebné, a preskupením udržujte vlastnosť haldy - preosiať dole.
Inšpekcia haldy
veľkosť
Viď vyššie!
je prázdny
Viď vyššie!
Ostatné triedy hald
Haldu popísanú v tomto článku možno považovať za hlavnú (všeobecnú) haldu. Existujú aj ďalšie triedy hromád. Avšak okrem toho by ste mali poznať dva, ktoré sú Binary Heap a D-Ary Heap.
Binárna halda
Binárna halda je podobná tejto hlavnej halde, ale má viac obmedzení. Najmä binárna hromada musí byť úplným stromom. Nezamieňajte medzi úplným stromom a plným stromom.
d-ary halda
Binárna halda je 2-árová halda. Hromada, v ktorej má každý uzol 3 deti, je hromada 3-Árov. Hromada, v ktorej má každý uzol 4 deti, je 4-hromadná hromada atď. Hromada typu d-ary má ďalšie obmedzenia.
Záver
Halda je úplný alebo takmer úplný binárny strom, ktorý spĺňa vlastnosť haldy. Vlastnosť haldy má dve alternatívy: pre maximálnu haldu musí mať rodič rovnakú alebo väčšiu hodnotu ako najbližšie deti; pre minimálnu hromadu musí mať rodič rovnakú alebo menšiu hodnotu ako najbližšie deti. Halda môže byť reprezentovaná ako strom alebo v poli. Keď je koreňový uzol zastúpený v poli, je jeho prvým uzlom; a ak je uzol na indexe n, jeho prvé dieťa v poli je na indexe 2n + 1 a jeho ďalšie dieťa je na indexe 2n + 2. Halda má určité operácie, ktoré sa vykonávajú s poľom.
Chrys
