Heap (datastruktur)

Inom datavetenskap är en heap en specialiserad datastruktur  av den trädtyp som uppfyller heap- egenskapen: om B är en undernod till nod A , då key( A ) ≥ key( B ). Det följer att elementet med den största nyckeln alltid är rotnoden för högen, så ibland kallas sådana högar max-högar (alternativt, om jämförelsen är omvänd, kommer det minsta elementet alltid att vara rotnoden, sådana högar kallas min-högar ). Det finns ingen begränsning för hur många barnnoder varje högnod har, även om detta antal i praktiken vanligtvis inte är fler än två. Högen är den mest effektiva implementeringen av en abstrakt datatyp som kallas en prioritetskö . Heaps är avgörande i vissa effektiva grafalgoritmer , som Dijkstras algoritm för d- heaps och heapsort .

Högdatastrukturen ska inte förväxlas med begreppet en heap i dynamisk minnesallokering . Termen användes först specifikt för datastrukturer. Några tidiga populära programmeringsspråk som LISP tillhandahöll dynamisk minnesallokering med hjälp av "heap" datastrukturen, som gav sitt namn till den tilldelade mängden minne. [1] .

Högar implementeras vanligtvis som arrayer, vilket eliminerar behovet av pekare mellan dess element.

Följande operationer utförs vanligtvis på högar:

• hitta max eller finn minimum : hitta maxelementet i maxhögen respektive minimumelementet i minhögen
• ta bort max eller ta bort min : ta bort rotnoden i max- respektive min-högen
• inkrementnyckel eller dekrementeringsnyckel : uppdateringsnyckel i max- respektive min-hög
• add : Lägg till en ny nyckel till högen.
• sammanfoga : sammanfoga två högar för att skapa en ny hög som innehåller alla element från båda de ursprungliga.

Alternativ

• 2-3 högar
• biparent hög
• binär hög
• binomial hög
• Brodals kö
• Hög med D-barn
• fibonacci hög
• Hög med prioritet längst till vänster
• Tvillinghög
• asymmetrisk hög
• mjuk lugg
• Ternär hög
• kartesiskt träd

Jämförelse av teoretiska uppskattningar av varianter

Nedan finns uppskattningar av tidskomplexiteten för beräkningar för operationer på vissa typer av högar. [1] Där ett värde är markerat med en asterisk baseras uppskattningen på amorteringsanalys (sämsta tidpunkt), annars är uppskattningen ett vanligt värsta fall. O(F) ger en asymptotisk övre gräns, och Θ(F) är en asymptotiskt exakt uppskattning (se notationen "O" stor och "o" liten ). Operationsnamnen väljs för min-högen.

(*) Amorteringstid
(**) Där n är storleken på den största högen

Observera att "Brodals kö" är en implementering av en parallell prioritetskö utvecklad av en grupp ledd av Gert Brodal. [3]

Applikation

Högdatastrukturer har många användningsområden.

• Heapsort : En av de bästa sorteringsmetoderna som används som inte har kvadratiska worst-case scenarier.
• Sökalgoritmer: När du använder en hög kan sökning efter minimum, maximum, båda, medianen eller det k: te största elementet göras i linjär tid (ofta även i konstant tid). [fyra]
• Grafalgoritmer : Att använda högen som datastruktur för den interna genomgången resulterar i en minskning av körtiden med en polynomordning. Exempel på sådana problem är Prims konstruktionsalgoritm för minsta spännträd och Dijkstras problem med kortaste vägen .

En komplett och nästan komplett binär hög kan representeras på ett mycket effektivt sätt med hjälp av en indexmatris . Det första (eller sista) elementet kommer att innehålla roten. De följande två elementen i arrayen innehåller rotens undernoder. De nästa fyra elementen innehåller fyra barn från två noder som är barn till roten osv. Således kommer barnen i nivånoden natt vara placerade vid positioner 2noch 2n+1för en array indexerad från en, eller vid positioner 2n+1och 2n+2för en array indexerad från noll. Detta gör att du kan flytta upp eller ner i trädet genom att göra enkla arrayindexberäkningar. Högbalansering görs genom att omarrangera element som är ur funktion. Eftersom vi kan bygga en heap med hjälp av en array utan extra minne (för noder, till exempel), kan vi använda heapsort för att sortera arrayen på plats.

Implementeringar

• C++ Standard Template Library tillhandahåller funktionsmallar för heaphantering make_heap, push_heap och pop_heap (binära heaps är vanligtvis implementerade) som fungerar på iteratorer med slumpmässig åtkomst . Metoderna använder iteratorer som arrayreferenser och utför array-to-heap-konvertering.
• Java 2 Platform Java Pattern Set (från och med version 1.5) tillhandahåller en binär heap-implementering i klassen java.util.PriorityQueue<E>.
• Python har en heapq-modul som implementerar prioritetsköer med hjälp av en binär hög. [5]
• Sedan version 5.3 av PHP är metoderna maxheap (SplMaxHeap) och minheap (SplMinHeap) tillgängliga i standardbiblioteket.
• Perl har implementeringar av binär-, binomial- och fibonacci-högarna i Comprehensive Archive Network . [6]

Se även

• Stack
• Sorteringsalgoritm

Anteckningar

1. ↑ 1 2 3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduktion till algoritmer. MIT Press / McGraw-Hill.
2. ↑ Iacono, John (2000), Förbättrade övre gränser för parning av högar , Proc. 7th Scandinavian Workshop on Algorithm Theory , vol. 1851, Lecture Notes in Computer Science, Springer-Verlag, sid. 63–77 , DOI 10.1007/3-540-44985-X_5 
3. ↑ A Parallel Priority Queue with Constant Time Operations , < http://www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf > Arkiverad 26 juli 2011 på Wayback Machine 
4. ↑ Frederickson, Greg N. (1993), En Optimal Algorithm for Selection in a Min-Heap , Information and Computation , vol. 104, Academic Press, sid. 197–214, doi : 10.1006/inco.1993.1030 , < http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf > Arkiverad 3 december 2012 på Wayback Machine 
5. ↑ Python heapq . Hämtad 31 maj 2011. Arkiverad från originalet 18 oktober 2012. (obestämd)
6. ↑ Perl Heap