Halda (datová struktura)

V informatice je halda specializovaná datová struktura stromového typu ,  která splňuje vlastnost haldy : pokud B je podřízený uzel uzlu A , pak key( A ) ≥ key( B ). Z toho vyplývá, že prvek s největším klíčem je vždy kořenový uzel haldy, takže někdy se takové haldy nazývají max-heaps (alternativně, pokud je srovnání obráceno, nejmenším prvkem bude vždy kořenový uzel, takové haldy se nazývají min-hromady ). Neexistuje žádné omezení, kolik podřízených uzlů má každý uzel haldy, i když v praxi tento počet obvykle není větší než dva. Halda je nejúčinnější implementací abstraktního datového typu nazývaného prioritní fronta . Hromady jsou klíčové v některých efektivních grafových algoritmech , jako je Dijkstrův algoritmus pro d-hromady a heapsort .

Struktura dat haldy by neměla být zaměňována s konceptem haldy v dynamické alokaci paměti . Termín byl poprvé použit speciálně pro datové struktury. Některé rané populární programovací jazyky, jako je LISP , poskytovaly dynamickou alokaci paměti pomocí datové struktury „haldy“, která dala jméno přidělenému množství paměti. [1] .

Haldy jsou obvykle implementovány jako pole, což eliminuje potřebu ukazatelů mezi jejími prvky.

Na hromadách se obvykle provádějí následující operace:

• najděte maximum nebo najděte minimum : najděte maximální prvek v maximální haldě nebo minimální prvek v minimální haldě
• remove max nebo remove min : odstranění kořenového uzlu v max- nebo min-hromadě, v daném pořadí
• inkrementační klíč nebo dekrementační klíč : aktualizovat klíč v maximální nebo minimální haldě
• add : Přidání nového klíče do haldy.
• merge : spojení dvou hromad za účelem vytvoření nové hromady obsahující všechny prvky obou původních.

Možnosti

• 2-3 hromada
• dvourodá hromada
• binární halda
• binomická hromada
• Brodalova fronta
• Hromada s D dětmi
• Fibonacciho hromada
• Halda s prioritou nejvíce vlevo
• Dvojitá hromada
• asymetrická hromada
• měkká hromada
• Ternární halda
• karteziánský strom

Srovnání teoretických odhadů variant

Níže jsou uvedeny odhady časové složitosti výpočtů pro operace na určitých typech hald. [1] Je- li hodnota označena hvězdičkou, je odhad založen na analýze amortizace (nejhorší doba), jinak je odhad běžný nejhorší případ. O(F) udává asymptotickou horní hranici a Θ(F) je asymptoticky přesný odhad (viz označení „O“ velké a „o“ malé ). Názvy operací jsou vybrány pro min-hromadu.

(*) Doba amortizace
(**) Kde n je velikost největší haldy

Všimněte si, že "Brodalova fronta" je implementací paralelní prioritní fronty vyvinuté skupinou vedenou Gertem Brodalem. [3]

Aplikace

Datové struktury haldy mají mnoho využití.

• Heapsort : Jedna z nejlepších používaných metod třídění, která nemá kvadratické scénáře nejhoršího případu.
• Algoritmy vyhledávání: Při použití haldy lze hledání minima, maxima, obou, mediánu nebo k -tého největšího prvku provádět v lineárním čase (často dokonce v konstantním čase). [čtyři]
• Grafové algoritmy : Použití haldy jako datové struktury pro interní procházení vede ke zkrácení doby běhu o polynomiální pořadí. Příklady takových problémů jsou Primův algoritmus konstrukce minimálního spanning tree a Dijkstrův problém nejkratší cesty .

Kompletní a téměř kompletní binární haldu lze reprezentovat velmi efektivním způsobem pomocí indexového pole . První (nebo poslední) prvek bude obsahovat kořen. Další dva prvky pole obsahují podřízené uzly kořene. Další čtyři prvky obsahují čtyři potomky ze dvou uzlů, které jsou potomky kořene atd. Potomci uzlu úrovně nbudou tedy umístěni na pozicích 2na 2n+1pro pole indexované z jednoho nebo na pozicích 2n+1a 2n+2pro pole indexované od nuly. To vám umožňuje pohybovat se ve stromu nahoru nebo dolů pomocí jednoduchých výpočtů indexu pole. Vyvažování haldy se provádí přeskupením prvků, které jsou mimo provoz. Protože můžeme vytvořit haldu pomocí pole bez další paměti (například pro uzly), můžeme použít heapsort k seřazení pole na místě.

Implementace

• Knihovna standardních šablon C++ poskytuje šablony funkcí pro správu haldy make_heap, push_heap a pop_heap (obvykle jsou implementovány binární haldy), které fungují na iterátorech s náhodným přístupem . Metody používají iterátory jako odkazy na pole a provádějí převod pole na haldu.
• Sada Java 2 Platform Java Pattern Set (od verze 1.5) poskytuje implementaci binární haldy ve třídě java.util.PriorityQueue<E>.
• Python má modul heapq, který implementuje prioritní fronty pomocí binární haldy. [5]
• Od verze 5.3 PHP jsou ve standardní knihovně dostupné metody maxheap (SplMaxHeap) a minheap (SplMinHeap).
• Perl má implementace binárních, binomických a fibonacciho hromad v Comprehensive Archive Network . [6]

Viz také

• Zásobník
• Algoritmus řazení

Poznámky

1. ↑ 1 2 3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Úvod do algoritmů. MIT Press / McGraw-Hill.
2. ↑ Iacono, John (2000), Vylepšené horní hranice pro párování hromad , Proc. 7th Scandinavian Workshop on Algorithm Theory , sv. 1851, Poznámky k přednáškám z informatiky, Springer-Verlag, s. 63–77 , DOI 10.1007/3-540-44985-X_5 
3. ↑ Paralelní prioritní fronta s operacemi s konstantním časem , < http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf > Archivováno 26. července 2011 na Wayback Machine 
4. ↑ Frederickson, Greg N. (1993), Optimal Algorithm for Selection in a Min-Heap , Information and Computation , sv. 104, Academic Press, s. 197–214, doi : 10.1006/inco.1993.1030 , < http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf > Archivováno 3. prosince 2012 na Wayback Machine 
5. ↑ Python heapq . Získáno 31. května 2011. Archivováno z originálu 18. října 2012. (neurčitý)
6. ↑ Perl Heap