Heap (datastruktur) - Heap (data structure)
I datalogi , en bunke er en specialiseret træ baseret datastruktur som er hovedsagelig en næsten komplet træ, der tilfredsstiller den bunke ejendom : i en max bunke , for en given node C, hvis P er en forælder node af C, så nøglen ( værdien ) af P er større end eller lig med nøglen til C. I en mindebunke er nøglen til P mindre end eller lig med nøglen til C. Knuden på "toppen" af bunken (uden forældre) kaldes root node.
Bunken er en maksimalt effektiv implementering af en abstrakt datatype kaldet en prioritetskø , og faktisk omtales prioritetskøer ofte som "bunker", uanset hvordan de kan implementeres. I en bunke er det højeste (eller laveste) prioritetselement altid gemt ved roden. En bunke er imidlertid ikke en sorteret struktur; det kan betragtes som værende delvist bestilt. En bunke er en nyttig datastruktur, når det er nødvendigt gentagne gange at fjerne objektet med den højeste (eller laveste) prioritet.
En almindelig implementering af en bunke er den binære bunke , hvor træet er et binært træ (se figur). Heap -datastrukturen , specifikt den binære bunke, blev introduceret af JWJ Williams i 1964 som en datastruktur for heapsort -sorteringsalgoritmen. Bunger er også afgørende i flere effektive grafalgoritmer, såsom Dijkstras algoritme . Når en bunke er et komplet binært træ, har den en mindst mulig højde - en bunke med N -noder og for hver knude har en gren altid en N -højde.
Bemærk, at der, som vist på grafikken, ikke er nogen underforstået rækkefølge mellem søskende eller fætre og ingen underforstået sekvens for en gennemgående traversal (som der ville være i f.eks. Et binært søgetræ ). Det ovennævnte bunkeforhold gælder kun mellem knuder og deres forældre, bedsteforældre osv. Det maksimale antal børn, hver knude kan have, afhænger af bunketypen.
Operationer
De almindelige operationer, der involverer dynger, er:
- Grundlæggende
- find-max (eller find-min ): find en maksimal genstand på henholdsvis en max-heap eller et minimum-element i en min-heap (aka peek )
- indsæt : tilføjelse af en ny nøgle til bunken (aka, skub )
- extract-max (eller extract-min ): returnerer noden med maksimal værdi fra en maksimal bunke [eller minimumsværdi fra en minheap] efter at have fjernet den fra bunken (aka, pop )
- delete-max (eller delete-min ): fjernelse af rodnoden for henholdsvis en max-heap (eller min-heap)
- erstat : pop rod og tryk på en ny nøgle. Mere effektiv end pop efterfulgt af push, da det kun er nødvendigt at balancere én gang, ikke to gange, og passende til masser af faste størrelser.
- Skabelse
- create-heap : opret en tom bunke
- heapify : opret en bunke ud af et givet array af elementer
- fletning ( forening ): sammenføjning af to dynger for at danne en gyldig ny bunke, der indeholder alle elementerne i begge dele, bevarelse af de originale dynger.
- meld : sammenføjning af to bunker for at danne en gyldig ny bunke, der indeholder alle elementerne i begge dele, og ødelægger de originale bunker.
- Inspektion
- størrelse : returner antallet af varer i bunken.
- er-tom : returner sandt, hvis bunken er tom, ellers falsk.
- Indre
- øge-nøgle eller fald-nøgle : opdatering af en nøgle inden for henholdsvis en maks- eller min-bunke
- slet : slet en vilkårlig knude (efterfulgt af at flytte sidste knude og sigtes for at opretholde bunke)
- sigtning : flyt en knude op i træet, så længe det er nødvendigt; bruges til at gendanne bunketilstand efter indsættelse. Kaldes "sigte", fordi knude bevæger sig op i træet, indtil det når det korrekte niveau, som i en sigte .
- sigt-ned : flyt en knude ned i træet, svarende til sigtning; bruges til at gendanne bunketilstand efter sletning eller udskiftning.
Implementering
Bunker implementeres normalt med en matrix som følger:
- Hvert element i arrayet repræsenterer en node af bunken og
- Forælder / barn -forholdet er defineret implicit af elementernes indeks i arrayet.
For en binær bunke i arrayet indeholder det første indeks rodelementet. De næste to indekser i arrayet indeholder rodens børn. De næste fire indekser indeholder de fire børn af rodens to barneknuder og så videre. I betragtning af en knude ved indeks i er dets børn derfor ved indekserne 2i + 1 og 2i + 2 , og dets forælder er ved indekset ⌊ (i − 1)/2⌋ . Denne enkle indekseringsordning gør det effektivt at flytte "op" eller "ned" i træet.
Balancering af en bunke udføres ved sigtning eller sigtning (udskiftning af elementer, der er ude af drift). Da vi kan bygge en bunke fra et array uden at kræve ekstra hukommelse (f.eks. Til noder), kan heapsort bruges til at sortere en array in-place.
Efter at et element er indsat i eller slettet fra en bunke, kan bunkegenskaben blive krænket, og bunken skal balanceres igen ved at bytte elementer i arrayet.
Selvom forskellige typer dynger implementerer operationerne forskelligt, men den mest almindelige måde er som følger:
Indsættelse: Tilføj det nye element i slutningen af bunken i den første ledige ledige plads. Dette vil krænke bunkejendommen, så elementerne forskydes op (eller svømmedrift ), indtil bunkejendommen er blevet genetableret.
Ekstraktion: Fjern rod og indsæt det sidste element i den bunke i roden, og dette vil krænke bunke ejendom, så, støvtætte ned for at genetablere den bunke ejendom (eller vask drift). Således udskiftes det ved at slette roden og sætte det nye element i roden og sile ned, undgå et sigtningstrin sammenlignet med pop (sigt ned af sidste element) efterfulgt af skub (sigt op af nyt element).
Konstruktion af en binær (eller d -ary) bunke ud af et givet array af elementer kan udføres i lineær tid ved hjælp af den klassiske Floyd -algoritme , med det værst tænkelige antal sammenligninger lig med 2 N -2 s 2 ( N ) - e 2 ( N ) (for en binær heap), hvor s 2 ( N ) er summen af alle cifre i den binære repræsentation af N og e 2 ( N ) er eksponenten af 2 i det primære faktorisering af N . Dette er hurtigere end en sekvens af på hinanden følgende indsættelser i en oprindeligt tom bunke, som er log-lineær.
Varianter
Sammenligning af teoretiske grænser for varianter
Her er tidskomplekser i forskellige bunke datastrukturer. Funktionsnavne antager en maksimal bunke. For betydningen af " O ( f )" og " Θ ( f )" se Big O -notation .
| Operation | find-max | slet-max | indsæt | øge-nøgle | meld |
|---|---|---|---|---|---|
| Binær | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Venstreorienteret | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Binomial | Θ (1) | Θ (log n ) | Θ (1) | Θ (log n ) | O (log n ) |
| Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Parring | Θ (1) | O (log n ) | Θ (1) | o (log n ) | Θ (1) |
| Brodal | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Rangparring | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Strenge Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2–3 bunke | O (log n ) | O (log n ) | O (log n ) | Θ (1) | ? |
Ansøgninger
Heap -datastrukturen har mange applikationer.
- Heapsort : En af de bedste sorteringsmetoder, der er på plads og uden kvadratiske worst-case scenarier.
- Udvælgelsesalgoritmer : En bunke giver adgang til min- eller max-elementet i konstant tid, og andre valg (f.eks. Median- eller kth-element) kan foretages i sub-lineær tid på data, der er i en bunke.
- Grafalgoritmer : Ved at bruge dynger som interne traversale datastrukturer reduceres køretiden med polynomisk rækkefølge. Eksempler på sådanne problemer er Prims algoritme med minimal spændingstræ og Dijkstras algoritme med korteste vej .
- Prioritetskø : En prioritetskø er et abstrakt begreb som "en liste" eller "et kort"; ligesom en liste kan implementeres med en sammenkædet liste eller et array, kan en prioritetskø implementeres med en bunke eller en række andre metoder.
- K-way fusion : En bunke datastruktur er nyttig til at flette mange allerede sorterede inputstrømme til en enkelt sorteret output stream. Eksempler på behovet for sammenlægning omfatter ekstern sortering og streaming af resultater fra distribuerede data, f.eks. Et log -struktureret fusionstræ. Den indre sløjfe opnår min-elementet, erstatter med det næste element for den tilsvarende inputstrøm og foretager derefter en sigtning af bunkeoperation. (Alternativt er udskiftningsfunktionen.) (Brug af extract-max og insert-funktioner i en prioritetskø er meget mindre effektiv.)
- Ordrestatistik : Heap -datastrukturen kan bruges til effektivt at finde det kth mindste (eller største) element i en array.
Programmeringssprogimplementeringer
- The C ++ Standard Library tilvejebringer make_heap , push_heap og pop_heap algoritmer til dynger (sædvanligvis implementeret som binære dynger), der opererer på vilkårlige random access iteratorer . Det behandler iteratorerne som en reference til et array og bruger array-to-heap-konverteringen. Det giver også beholderadapter prioritet_kø , som indpakker disse faciliteter i en containerlignende klasse. Der er imidlertid ingen standard understøttelse af udskiftning, sigtning op/sigtning ned eller fald/forøgelse af nøglefunktioner.
- De Boost C ++ biblioteker omfatter en dynger bibliotek. I modsætning til STL understøtter det fald og forøgelse af operationer og understøtter yderligere typer bunker: specifikt understøtter det d -ary, binomial, Fibonacci, parring og skæv bunke.
- Der er en generisk bunkeimplementering til C og C ++ med D-ary bunke og B-heap support. Det giver en STL-lignende API.
- Standardbiblioteket for D -programmeringssprog inkluderer std.container.BinaryHeap , som er implementeret med hensyn til D's intervaller . Instanser kan konstrueres ud fra ethvert vilkårligt adgangsområde . BinaryHeap afslører en inputinterface- grænseflade, der tillader iteration med D's indbyggede foreach- sætninger og integration med den rækkebaserede API for std.algoritme- pakken .
- Den Java- platformen (siden version 1.5) giver en binær heap implementering med klassen
java.util.PriorityQueuei Java Samlinger Framework . Denne klasse implementerer som standard en min-bunke; for at implementere en max-heap, bør programmør skrive en brugerdefineret komparator. Der er ingen understøttelse af udskiftning, sigtning op/sigt-ned eller fald/forøgelse af nøglefunktioner. - Python har et heapq -modul, der implementerer en prioritetskø ved hjælp af en binær bunke. Biblioteket udsætter en heapreplace-funktion for at understøtte fletning af k-vejs.
- PHP har både max-heap ( SplMaxHeap ) og min-heap ( SplMinHeap ) fra version 5.3 i Standard PHP-biblioteket.
- Perl har implementeringer af binære, binomiske og Fibonacci -dynger i Heap -distributionen tilgængelig på CPAN .
- Den Go sprog indeholder en bunke pakke med heap algoritmer, der opererer på en vilkårlig type, der opfylder en given grænseflade. Denne pakke understøtter ikke udskiftning, sigtning op/sigtning ned eller nedsættelse/forøgelse af nøglefunktioner.
- Apples Core Foundation -bibliotek indeholder en CFBinaryHeap -struktur.
- Pharo har implementering af en bunke i pakken Collections-Sequenceable sammen med et sæt testcases. En bunke bruges til implementering af timerhændelsesløkken.
- Den Rust programmeringssprog har en binær max-heap implementering, BinaryHeap , i samlingerne modul i sin standard bibliotek.
Se også
- Sorteringsalgoritme
- Søg datastruktur
- Stak (abstrakt datatype)
- Kø (abstrakt datatype)
- Træ (datastruktur)
- Treap , en form for binært søgetræ baseret på bunkeordnede træer
Referencer
eksterne links
- Bunke hos Wolfram MathWorld
- Forklaring på, hvordan de grundlæggende bunke -algoritmer fungerer
- Bentley, Jon Louis (2000). Programmeringsperler (2. udgave). Addison Wesley. s. 147–162. ISBN 0201657880.