Binær bunke

En binær bunke , en pyramide [1] eller et sorteringstræ er et binært træ , der opfylder tre betingelser:

Værdien ved ethvert toppunkt er ikke mindre end værdierne af dets efterkommere [K 1] .
Dybden af alle blade (afstand til roden) afviger ikke med mere end 1 lag.
Det sidste lag fyldes fra venstre mod højre uden "huller".

Der er også dynger, hvor værdien ved ethvert toppunkt tværtimod ikke er større end værdierne for dens efterkommere. Sådanne dynger kaldes min-heap, og dyngerne beskrevet ovenfor kaldes max-heap. I det følgende betragtes kun max-heap. Alle handlinger med min-heap udføres på samme måde.

En bekvem datastruktur for et sorteringstræ er en matrix A , hvis første element, A [1] er elementet ved roden, og børnene af element A [ i ] er A [2 i ] og A [2 i +1 ] (ved nummerering af elementer med først). Når elementer nummereres fra nul, er rodelementet A [0], og børnene af elementet A [ i ] er A [2 i +1] og A [2 i +2]. Med denne opbevaringsmetode opfyldes betingelser 2 og 3 automatisk.

Højden af bunken er defineret som højden af det binære træ. Det vil sige, at det er lig med antallet af kanter i den længste enkle sti, der forbinder roden af bunken med et af dens blade. Højden er , hvor N er antallet af træknuder. $\Theta \left(\log {N}\right)$

Funktionalitet

Du kan udføre følgende handlinger på en heap:

Tilføj et element til bunken. Kompleksitet $O(\log{n})$
Fjern det maksimale element fra bunken. Arbejdstimer $O(\log{n})$
Skift værdien af ethvert element. Arbejdstimer $O(\log{n})$

Baseret på disse handlinger kan du udføre følgende handlinger:

Gør en uordnet række af elementer til en bunke. Kompleksitet $På)$
Sorter en matrix ved at omdanne den til en heap og heapen til en sorteret matrix. Arbejdstimer $O(n\log{n})$

Her er antallet af heap-elementer. Rumkompleksitet - for alle ovenstående operationer og aktiviteter. $n$ $O(1)$

En detaljeret beskrivelse og algoritmer af disse handlinger og den Heapify-procedure, der kræves for at udføre dem, er givet i næste afsnit.

Grundlæggende procedurer

Dette afsnit introducerer de grundlæggende procedurer for at arbejde med en heap.

Gendannelse af heap-egenskaber

Hvis et af elementerne i heapen ændres, så opfylder det muligvis ikke længere bestillingsegenskaben. For at gendanne denne egenskab skal du bruge Heapify-proceduren. Det gendanner heap-egenskaben i et træ, hvis venstre og højre undertræ opfylder det. Denne procedure tager som input et array af elementer A og indeks i . Den gendanner bestillingsegenskaben i hele undertræet, hvis rod er elementet A [ i ].

Hvis det i -te element er større end dets børn, er hele undertræet allerede en bunke, og der skal ikke gøres noget. Ellers bytter vi det i -te element ud med det største af dets børn, hvorefter vi udfører Heapify for denne søn.

Proceduren afsluttes i tide . $O\venstre(\log {n}\højre)$

Heapify( A , i ) left ← 2 i right ← 2 i +1 heap_size - antallet af elementer i bunken størst ← i hvis venstre ≤ A . heap_size og A [ venstre ] > A [ størst ] så størst ← venstre hvis højre ≤ A. heap_size og A [ højre ] > A [ største ] så størst ← højre hvis størst ≠ i så Byt A [ i ] ↔ A [ største ] Heapify ( A , størst )

For sprog, der ikke understøtter automatisk halerekursionsoptimering , kan implementeringseffektiviteten forbedres ved at slippe af med rekursion.

Opbygning af en bunke

Denne procedure er designet til at skabe en heap ud fra en uordnet række af inputdata.

Bemærk, at hvis du udfører Heapify på alle elementer i array A, fra det sidste til det første, bliver det til en heap. Det er faktisk let at bevise ved induktion, at når Heapify(A, i) udføres, er alle undertræer, hvis rødder har et indeks større end i, dynger, og derfor, efter at Heapify(A, i) er udført, vil alle undertræer, hvis rødder har et indeks, der ikke er mindre end i.

Heapify(A,i) gør heller ikke noget, hvis i>N/2 (ved nummerering fra det første element), hvor N er antallet af array-elementer. Sådanne elementer har faktisk ingen børn, derfor er de tilsvarende undertræer allerede dynger, da de kun indeholder ét element.

Det er således tilstrækkeligt at kalde Heapify for alle elementer i array A, startende (når man nummererer fra det første element) fra -th og slutter med det første. $[N/2]$

Build_Heap( A ) A . heap_size ← A . længde for i ← ⌊ A . længde /2⌋ ned til 1 gør Heapify ( A , i )

Selvom der er n/2 kald til Heapify-funktionen her med kompleksitet , kan det vises, at køretiden er [1] . $O\venstre(\log {n}\højre)$ $På)$

Heap sortering

Heapsort-proceduren sorterer et array uden at bruge yderligere hukommelse i tide . $O\venstre(n\log {n}\højre)$

For at forstå dets funktion kan vi forestille os, at vi har udskiftet det første element (det vil sige roden) med det sidste. Så vil det sidste element være det største. Hvis vi derefter udelukker det sidste element fra bunken (det vil sige formelt reducere dets længde med 1), vil de første N-1 elementer opfylde betingelserne for bunken alle, undtagen måske roden. Hvis du kalder Heapify, vil de første N-1 elementer blive til en heap, og den sidste vil være større end dem alle. Ved at gentage disse trin N-1 gange, sorterer vi arrayet.

Heapsort ( A ) Build_Heap( A ) for i ← A . længde ned til 1 do Byt A [1] ↔ A [ i ] A . heap_size ← A . heap_size -1 Heapify( A ,1)

Ændring af værdien af et element

Heap_Increase_Key-proceduren erstatter et heap-element med en ny nøgle med en værdi, der er større end eller lig med værdien af det originale element . Typisk bruges denne procedure til at tilføje et vilkårligt element til heapen. Tidskompleksitet . $O\venstre(\log {n}\højre)$

Hvis elementet er mindre end dets overordnede, er betingelse 1 opfyldt for hele træet, og intet andet skal gøres. Hvis han er større, bytter vi plads med hans far. Hvis faderen efter det er større end bedstefaren, bytter vi faren med farfaren og så videre. Med andre ord flyder et for stort element til toppen.

Heap_Increase_Key( A , i , key ) hvis tast < A [ i ] så fejlen "Den nye nøgle er mindre end den forrige" A [ i ] ← tast mens i > 1 og A [⌊ i /2⌋] < A [ i ] do Byt A [ i ] ↔ A [⌊ i /2⌋] i ← ⌊ i /2⌋

I det tilfælde, hvor det er nødvendigt at reducere værdien af et element, kan du kalde Heapify.

Tilføjelse af et element

Udfører tilføjelse af et element til heapen i tide . $O\venstre(\log {n}\højre)$

Tilføjelse af et vilkårligt element til slutningen af heapen og gendannelse af ordreegenskaben med Heap_Increase_Key.

Heap_Insert( A , key ) A . heap_size ← A . heap_size +1 A [ A . heap_size ] ← -∞ Heap_Increase_Key( A , A . heap_size , key)

Udpakning af det maksimale element

Henter det maksimale element fra heapen i tide . $O\venstre(\log {n}\højre)$

Ekstraktion udføres i fire trin:

værdien af rodelementet (det er maksimum) gemmes til senere returnering
det sidste element kopieres til roden og fjernes derefter fra dyngen
kaldet Heapify på roden
det gemte element returneres

Heap_Extract_Max( A ) hvis A . heap_size [ A ] < 1 derefter fejl "Heap er tom" max ← A [1] A [1] ← A [ A .heap_size] A . heap_size ← A . heap_size -1 Heapify( A , 1) return max

Se også

Kommentarer

↑ Hvis sorteringsrækkefølgen er omvendt, må værdien ved enhver node ikke være større end værdierne for dens efterkommere.

Datastrukturer
Lister	array enkelt linket liste dobbelt linket liste Beståelsesliste
Træer	B-træ Binært søgetræ AVL træ Rød-sort træ dynge
Tæller	Instrueret graf rettet acyklisk graf Binært beslutningsdiagram Hypergraf
Andet	Hash bord Stak

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol