Binární halda

Binární halda , pyramida [1] nebo třídící strom je binární strom , který splňuje tři podmínky:

Hodnota v žádném vrcholu není menší než hodnoty jeho potomků [K 1] .
Hloubka všech listů (vzdálenost ke kořeni) se neliší o více než 1 vrstvu.
Poslední vrstva se plní zleva doprava bez "otvorů".

Existují také hromady, kde hodnota v žádném vrcholu naopak není větší než hodnoty jeho potomků. Takové haldy se nazývají min-heap a haldy popsané výše se nazývají max-heap. V následujícím se uvažuje pouze maximální halda. Všechny akce s min-hromadou se provádějí podobně.

Vhodná datová struktura pro třídící strom je pole A , jehož první prvek, A [1] je prvek v kořenu, a potomci prvku A [ i ] jsou A [2 i ] a A [2 i +1 ] (při číslování prvků prvním). Při číslování prvků od nuly je kořenový prvek A [0] a potomci prvku A [ i ] jsou A [2 i +1] a A [2 i +2]. Při tomto způsobu skladování jsou podmínky 2 a 3 splněny automaticky.

Výška haldy je definována jako výška binárního stromu. To znamená, že se rovná počtu hran v nejdelší jednoduché cestě spojující kořen hromady s jedním z jejích listů. Výška haldy je , kde N je počet uzlů stromu. $\Theta \left(\log {N}\right)$

Funkčnost

Na hromadě můžete provádět následující operace:

Přidejte prvek do haldy. Složitost $O(\log{n})$
Odstraňte maximum prvku z hromady. Pracovní doba $O(\log{n})$
Změňte hodnotu libovolného prvku. Pracovní doba $O(\log{n})$

Na základě těchto operací můžete provádět následující akce:

Přeměňte neuspořádané pole prvků na hromadu. Složitost $Na)$
Seřaďte pole tak, že jej změníte na haldu a haldu na seřazené pole. Pracovní doba $O(n\log{n})$

Zde je počet prvků haldy. Prostorová složitost - pro všechny výše uvedené operace a akce. $n$ $O(1)$

Podrobný popis a algoritmy těchto akcí a postup Heapify potřebný k jejich provedení jsou uvedeny v další části.

Základní postupy

Tato část představuje základní postupy pro práci s haldou.

Obnovení vlastností haldy

Pokud se jeden z prvků v hromadě změní, nemusí již splňovat vlastnost ordering. Chcete-li obnovit tuto vlastnost, použijte proceduru Heapify. Obnovuje vlastnost haldy ve stromu, jehož levý a pravý podstrom ji uspokojuje. Tato procedura bere jako vstup pole prvků A a index i . Obnoví vlastnost řazení v celém podstromu, jehož kořenem je prvek A [ i ].

Pokud je i -tý prvek větší než jeho potomci, celý podstrom je již hromada a není třeba nic dělat. V opačném případě vyměníme i -tý prvek s největším z jeho potomků, načež provedeme Heapify pro tohoto syna.

Postup je dokončen včas . $O\left(\log {n}\vpravo)$

Heapify( A , i ) vlevo ← 2 i vpravo ← 2 i +1 velikost_hromady - počet prvků v hromadě největší ← i , pokud vlevo ≤ A . heap_size a A [ vlevo ] > A [ největší ], pak největší ← vlevo , pokud vpravo ≤ A. velikost_hromady a A [ vpravo ] > A [ největší ] pak největší ← vpravo , pokud největší ≠ i pak Vyměnit A [ i ] ↔ A [ největší ] Heapify ( A , největší )

U jazyků, které nepodporují automatickou optimalizaci koncové rekurze , lze efektivitu implementace zlepšit odstraněním rekurze.

Budování haldy

Tento postup je určen k vytvoření haldy z neuspořádaného pole vstupních dat.

Všimněte si, že pokud spustíte Heapify na všech prvcích pole A, od posledního po první, stane se haldou. Je skutečně snadné dokázat indukcí, že v době, kdy je Heapify(A,i) vykonáno, všechny podstromy, jejichž kořeny mají index větší než i, jsou hromady, a proto po provedení Heapify(A,i) jsou všechny podstromy, jejichž kořeny mají index ne menší než i.

Také Heapify(A,i) nedělá nic, pokud i>N/2 (při číslování od prvního prvku), kde N je počet prvků pole. Ve skutečnosti takové prvky nemají žádné potomky, takže odpovídající podstromy jsou již hromady, protože obsahují pouze jeden prvek.

Stačí tedy zavolat Heapify pro všechny prvky pole A, počínaje (při číslování od prvního prvku) od -tého a končícího prvním. $[N/2]$

Build_Heap( A ) A . velikost_hromady ← A . délka pro i ← ⌊ A . délka /2⌋ dolů na 1 do Heapify ( A , i )

Ačkoli je zde n/2 volání funkce Heapify se složitostí , lze ukázat, že doba běhu je [1] . $O\left(\log {n}\vpravo)$ $Na)$

Řazení haldy

Procedura Heapsort seřadí pole bez použití další paměti v čase . $O\left(n\log {n}\vpravo)$

Pro pochopení jeho fungování si můžeme představit, že jsme vyměnili první prvek (tedy kořen) za poslední. Pak bude poslední prvek největší. Pokud poté vyloučíme poslední prvek z haldy (tj. formálně zkrátíme jeho délku o 1), prvních N-1 prvků splní podmínky haldy všechny, snad kromě kořene. Pokud zavoláte Heapify, prvních N-1 prvků se stane hromadou a poslední bude větší než všechny. Opakováním těchto kroků N-1 krát seřadíme pole.

Heapsort ( A ) Build_Heap( A ) pro i ← A . délka downto 1 do Swap A [1] ↔ A [ i ] A . velikost_hromady ← A . velikost_hromady -1 Heapify ( A ,1)

Změna hodnoty prvku

Procedura Heap_Increase_Key nahradí prvek haldy novým klíčem s hodnotou větší nebo rovnou hodnotě původního prvku . Obvykle se tento postup používá k přidání libovolného prvku do haldy. Časová složitost . $O\left(\log {n}\vpravo)$

Pokud je prvek menší než jeho rodič, podmínka 1 je splněna pro celý strom a není třeba dělat nic jiného. Pokud je větší, vyměníme si místo s jeho otcem. Pokud je potom otec větší než dědeček, vyměníme otce s dědečkem a tak dále. Jinými slovy, příliš velký prvek vyplave nahoru.

Heap_Increase_Key( A , i , klíč ) pokud klíč < A [ i ], pak chyba "Nový klíč je menší než předchozí" Klíč [ i ] ← zatímco i > 1 a A [⌊ i /2⌋] < A [ i ] do Swap A [ i ] ↔ A [⌊ i /2⌋] i ← ⌊ i /2⌋

V případě, že je nutné snížit hodnotu prvku, můžete zavolat Heapify.

Přidání prvku

Provede přidání prvku do haldy v čase . $O\left(\log {n}\vpravo)$

Přidání libovolného prvku na konec haldy a obnovení vlastnosti order pomocí Heap_Increase_Key.

Heap_Insert ( A , klíč ) A . velikost_hromady ← A . velikost_hromady +1 A [ A . velikost_hromady ] ← -∞ Heap_Increase_Key( A , A . velikost_hromady , klíč)

Extrahování maximálního prvku

Načte maximum prvku z haldy v čase . $O\left(\log {n}\vpravo)$

Extrakce se provádí ve čtyřech krocích:

hodnota kořenového prvku (je to maximum) je uložena pro pozdější návrat
poslední prvek je zkopírován do kořenového adresáře a poté odstraněn z haldy
s názvem Heapify na kořeni
uložený prvek je vrácen

Heap_Extract_Max( A ) , pokud A . velikost_hromady [ A ] < 1 pak chyba "Hromada je prázdná" max ← A [1] A [1] ← A [ A .velikost_hromady] A . velikost_hromady ← A . velikost_hromady -1 Heapify( A , 1) návrat max

Viz také

Odkazy

↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitola 6. Heapsort // Algoritmy: konstrukce a analýza = Úvod do algoritmů / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - S. 178 - 193. - ISBN 5-8459-0857-4 .

Komentáře

↑ Pokud je pořadí řazení obrácené, pak hodnota v žádném uzlu nesmí být větší než hodnoty jeho potomků.

Datové struktury
Seznamy	pole jednotlivě propojený seznam dvojitě propojený seznam Seznam průchodů
Stromy	B-strom Binární vyhledávací strom strom AVL Červeno-černý strom halda
Počítání	Orientovaný graf Orientovaný acyklický graf Binární rozhodovací diagram Hypergraf
jiný	Hash tabulka Zásobník

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree