Halda (datová struktura) - Heap (data structure)
V počítačové vědě je halda specializovanou datovou strukturou na bázi stromu , která je v podstatě téměř úplným stromem, který splňuje vlastnost haldy : v maximální hromadě pro jakýkoli daný uzel C, pokud P je nadřazený uzel C, pak klíč ( hodnota ) P je větší nebo rovna klíči C. V min. haldě je klíč P menší nebo rovný klíči C. Uzel v „horní části“ haldy (bez rodiče) se nazývá kořenový uzel.
Halda je jednou maximálně efektivní implementací abstraktního datového typu, kterému se říká prioritní fronta , a ve skutečnosti jsou prioritní fronty často označovány jako „hromady“, bez ohledu na to, jak mohou být implementovány. V hromadě je prvek s nejvyšší (nebo nejnižší) prioritou vždy uložen v kořenovém adresáři. Halda však není seřazená struktura; lze jej považovat za částečně objednaný. Halda je užitečná datová struktura, když je nutné opakovaně odebrat objekt s nejvyšší (nebo nejnižší) prioritou.
Běžnou implementací haldy je binární halda , ve které je strom binárním stromem (viz obrázek). Struktura haldy dat, konkrétně binární haldy, byl představen JWJ Williams v roce 1964, jako struktura dat pro heapsort třídění algoritmu. Haldy jsou také klíčové v několika efektivních grafových algoritmech, jako je Dijkstraův algoritmus . Když haldy je kompletní binární strom, má co nejmenší výšky hromadu s N uzly a pro každý uzel A větve má vždy přihlásit k N výšku.
Všimněte si, že, jak je znázorněno na obrázku, neexistuje žádné implikované řazení mezi sourozenci nebo bratranci a žádná implicitní sekvence pro přechod v pořadí (jako by to bylo například v binárním vyhledávacím stromu ). Výše uvedený vztah haldy platí pouze mezi uzly a jejich rodiči, prarodiči atd. Maximální počet dětí, které může každý uzel mít, závisí na typu haldy.
Operace
Běžné operace zahrnující hromady jsou:
- Základní
- find-max (nebo find-min ): najděte maximální položku max. haldy, respektive minimální položku min. haldy (aka peek )
- insert : přidání nového klíče do haldy (aka, push )
- extrahovat-max (nebo extrahovat-min ): vrací uzel maximální hodnoty z maximální hromady [nebo minimální hodnoty z minimální hromady] po odebrání z hromady (aka, pop )
- delete-max (nebo delete-min ): odebrání kořenového uzlu maximální hromady (nebo min. hromady)
- nahradit : pop root a stisknout nový klíč. Efektivnější než pop následovaný pushem, protože stačí vyvážit jednou, ne dvakrát a je vhodný pro hromady pevné velikosti.
- Tvorba
- create-heap : create an empty halda
- heapify : vytvoří hromadu z dané řady prvků
- sloučení ( sjednocení ): spojení dvou hromádek za vzniku platné nové hromady obsahující všechny prvky obou, zachování původních hromad.
- splynutí : spojení dvou hromádek za vzniku platné nové hromady obsahující všechny prvky obou a zničení původních hromádek.
- Inspekce
- velikost : vrátí počet položek v haldě.
- is-empty : return true, pokud je halda prázdná, false v opačném případě.
- Vnitřní
- klávesa pro zvýšení nebo snížení : aktualizace klíče v rámci maximální nebo minimální hromady
- odstranit : odstranění libovolného uzlu (následuje přesun posledního uzlu a prosévání, aby se zachovala hromada)
- sift-up : přesuňte uzel nahoru ve stromu, tak dlouho, jak je potřeba; slouží k obnovení stavu haldy po vložení. Nazývá se „prosévání“, protože uzel se pohybuje vzhůru po stromu, dokud nedosáhne správné úrovně, jako v sítu .
- sift-down : přesunutí uzlu dolů ve stromu, podobně jako pro třídění nahoru; slouží k obnovení stavu haldy po odstranění nebo výměně.
Implementace
Haldy se obvykle implementují s polem následujícím způsobem:
- Každý prvek v poli představuje uzel haldy a
- Vztah rodič / dítě je implicitně definován indexy prvků v poli.
U binární hromady v poli první index obsahuje kořenový prvek. Další dva indexy pole obsahují podřízené kořeny. Další čtyři indexy obsahují čtyři potomky dvou podřízených uzlů kořene atd. Vzhledem k tomu, že daný uzel v indexu i má jeho potomky indexy 2i + 1 a 2i + 2 a jeho nadřazený prvek je v indexu ⌊ (i − 1)/2⌋ . Toto jednoduché schéma indexování umožňuje pohybovat se stromem „nahoru“ nebo „dolů“.
Vyvažování hromady se provádí operacemi třídění nahoru nebo třídění dolů (prohození prvků, které jsou mimo provoz). Jelikož můžeme z pole sestavit hromadu, aniž bychom vyžadovali další paměť (například pro uzly), lze k třídění pole na místě použít heapsort .
Poté, co je prvek vložen do haldy nebo odstraněn z haldy, může být narušena vlastnost haldy a halda musí být znovu vyvážena výměnou prvků v poli.
Ačkoli různé typy haldy implementují operace odlišně, ale nejběžnější způsob je následující:
Vložení: Přidejte nový prvek na konec haldy, do prvního dostupného volného místa. To naruší vlastnost haldy, takže prvky budou posunuty nahoru (nebo operace plavání ), dokud nebude vlastnost haldy obnovena.
Extrakce: Odeberte kořen a vložte poslední prvek haldy do kořenového adresáře, čímž dojde k narušení vlastnosti haldy, takže seřaďte dolů a obnovte vlastnost haldy (nebo operaci jímky ). Nahrazování se tedy provádí odstraněním kořenového adresáře a vložením nového prvku do kořenového adresáře a prosetím dolů, čímž se zamezí kroku prosévání ve srovnání s popem (posun dolů posledního prvku), po kterém následuje push (prosazení nového prvku).
Konstrukci binární (nebo d -aryální) hromady z daného pole prvků lze provést v lineárním čase pomocí klasického Floydova algoritmu , přičemž počet nejhorších případů srovnání je 2 N -2 s 2 ( N ) - e 2 ( N ) (pro binární haldy), kde to 2 ( N ) je součet všech číslic binární reprezentaci N a e 2 ( N ) je exponent 2 v nultý faktorizaci N . To je rychlejší než sekvence po sobě jdoucích vložení do původně prázdné hromady, která je log-lineární.
Varianty
Porovnání teoretických hranic pro varianty
Zde jsou časové složitosti různých hromadných datových struktur. Názvy funkcí předpokládají max. Haldu. K významu „ O ( f )“ a „ t Vstup ( f )“ vidět velký O notace .
| Úkon | najít-max | smazat-max | vložit | klíč pro zvýšení | splynout |
|---|---|---|---|---|---|
| Binární | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Levicový | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Binomický | Θ (1) | Θ (log n ) | Θ (1) | Θ (log n ) | O (log n ) |
| Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Párování | Θ (1) | O (log n ) | Θ (1) | o (log n ) | Θ (1) |
| Brodal | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Párování hodností | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Přísný Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2–3 haldy | O (log n ) | O (log n ) | O (log n ) | Θ (1) | ? |
Aplikace
Hromadná datová struktura má mnoho aplikací.
- Heapsort : Jedna z nejlepších metod třídění na místě a bez kvadratických scénářů nejhorších případů.
- Algoritmy výběru : Hromada umožňuje přístup k prvku min nebo max v konstantním čase a další výběry (například medián nebo prvek kth) lze provádět v sublineárním čase na datech, která jsou v hromadě.
- Algoritmy grafu : Použitím hromádek jako interních traverzálních datových struktur se doba běhu zkrátí o polynomiální pořadí. Příklady takových problémů jsou Primův algoritmus minimálního překlenutí stromu a Dijkstraův algoritmus nejkratší cesty .
- Prioritní fronta : Fronta priorit je abstraktní koncept jako „seznam“ nebo „mapa“; stejně jako lze seznam implementovat pomocí propojeného seznamu nebo pole, lze prioritní frontu implementovat hromadou nebo řadou dalších metod.
- Sloučení K-way : Hromadná datová struktura je užitečná pro sloučení mnoha již seřazených vstupních proudů do jednoho seřazeného výstupního proudu. Mezi příklady potřeby sloučení patří výsledky externího třídění a streamování z distribuovaných dat, jako je strom sloučení strukturovaný do protokolu. Vnitřní smyčka získává prvek min, který je nahrazen dalším prvkem pro odpovídající vstupní proud, a poté provede operaci haldy prohledávání. (Alternativně funkce nahrazení.) (Použití funkcí extract-max a insert prioritní fronty je mnohem méně efektivní.)
- Statistiky objednávek : Datovou strukturu haldy lze použít k efektivnímu nalezení kth nejmenšího (nebo největšího) prvku v poli.
Implementace programovacího jazyka
- Standardní knihovna C ++ poskytuje make_heap , push_heap a pop_heap algoritmy pro hromad (obvykle implementován jako binární hromadách), které fungují na libovolných náhodného přístupu iterátory . Zachází s iterátory jako s odkazem na pole a používá převod z pole na haldu. Poskytuje také adaptér kontejneru priority_queue , který zabalí tato zařízení do třídy podobné kontejneru. Neexistuje však standardní podpora pro operace výměny, třídění nahoru/třídění dolů nebo snižování/zvyšování.
- Tyto Zesílení C ++ knihovny například: knihovna hromady. Na rozdíl od STL podporuje operace snižování a zvyšování a podporuje další typy haldy: konkrétně podporuje d -ary, binomické, Fibonacci, párování a zkosení haldy.
- Existuje obecná implementace haldy pro C a C ++ s podporou D-ary haldy a B-haldy . Poskytuje API podobné STL.
- Standardní knihovna D programovacího jazyka zahrnuje std.container.BinaryHeap , který se provádí, pokud jde o D je rozsahů . Instance lze sestavit z libovolného rozsahu náhodného přístupu . BinaryHeap vystavuje rozhraní vstupního rozsahu, které umožňuje iteraci s integrovanými příkazy foreach D a integraci s API založeným na rozsahu balíčku std.algorithm .
- Platforma Java (od verze 1.5) poskytuje implementaci binární haldy s třídou
java.util.PriorityQueuev Java Collections Framework . Tato třída ve výchozím nastavení implementuje min-haldu; k implementaci max. haldy by měl programátor napsat vlastní komparátor. Neexistuje žádná podpora pro operace výměny, třídění nahoru/třídění dolů nebo snižování/zvyšování. - Python má modul heapq, který implementuje prioritní frontu pomocí binární hromady. Knihovna vystavuje funkci heapreplace na podporu slučování k-way.
- PHP má od verze 5.3 ve standardní knihovně PHP jak max-haldu ( SplMaxHeap ), tak min-haldu ( SplMinHeap ).
- Perl má implementace binárních, binomických a Fibonacciho haldy v distribuci Heap dostupné na CPAN .
- Jazyk Go obsahuje balíček haldy s halpovými algoritmy, které fungují na libovolném typu, který vyhovuje danému rozhraní. Tento balíček nepodporuje operace výměny, třídění nahoru/třídění dolů ani snižování/zvyšování klíčů.
- Knihovna Core Foundation společnosti Apple obsahuje strukturu CFBinaryHeap .
- Pharo má implementaci hromady v balíčku Collect-Sequenceable spolu se sadou testovacích případů. Při implementaci smyčky událostí časovače se používá halda.
- Rust programovací jazyk má binární max-haldy implementace, binární halda , na tyto sbírky modulu standardní knihovny.
Viz také
- Algoritmus řazení
- Struktura dat vyhledávání
- Zásobník (abstraktní datový typ)
- Fronta (abstraktní datový typ)
- Strom (datová struktura)
- Treap , forma binárního vyhledávacího stromu založeného na hromadě uspořádaných stromů
Reference
externí odkazy
- Halda ve Wolfram MathWorld
- Vysvětlení toho, jak základní algoritmy haldy fungují
- Bentley, Jon Louis (2000). Programovací perly (2. vyd.). Addison Wesley. s. 147–162. ISBN 0201657880.