Binär hög

En binär hög , en pyramid [1] eller ett sorteringsträd  är ett binärt träd som uppfyller tre villkor:

  1. Värdet vid någon vertex är inte mindre än värdena för dess ättlingar [K 1] .
  2. Djupet på alla blad (avstånd till roten) skiljer sig inte med mer än 1 lager.
  3. Det sista lagret fylls från vänster till höger utan "hål".

Det finns också högar där värdet vid någon vertex, tvärtom, inte är större än värdena för dess ättlingar. Sådana högar kallas min-hög, och högarna som beskrivs ovan kallas max-hög. I det följande beaktas endast max-heap. Alla åtgärder med min-heap utförs på liknande sätt.

En lämplig datastruktur för ett sorteringsträd är en matris A , vars första element, A [1] är elementet vid roten, och barnen till element A [ i ] är A [2 i ] och A [2 i +1 ] (vid numrering av element med först). Vid numrering av element från noll är rotelementet A [0], och barnen till elementet A [ i ] är A [2 i +1] och A [2 i +2]. Med denna lagringsmetod uppfylls villkor 2 och 3 automatiskt.

Höjden på högen definieras som höjden på det binära trädet. Det vill säga, det är lika med antalet kanter i den längsta enkla vägen som förbinder roten av högen med ett av dess blad. Höghöjden är , där N  är antalet trädnoder.

Funktionalitet

Du kan utföra följande operationer på en hög:

Baserat på dessa operationer kan du utföra följande åtgärder:

Här  är antalet högelement. Utrymmeskomplexitet  - för alla ovanstående operationer och åtgärder.

En detaljerad beskrivning och algoritmer för dessa åtgärder och Heapify-proceduren som krävs för att utföra dem ges i nästa avsnitt.

Grundläggande procedurer

Det här avsnittet introducerar de grundläggande procedurerna för att arbeta med en heap.

Återställer högegenskaper

Om ett av elementen i högen ändras, kanske det inte längre uppfyller beställningsegenskapen. För att återställa den här egenskapen, använd Heapify-proceduren. Den återställer högegenskapen i ett träd vars vänstra och högra underträd uppfyller den. Denna procedur tar som indata en array av element A och index i . Den återställer beställningsegenskapen i hela underträdet vars rot är elementet A [ i ].

Om det i -te elementet är större än dess underordnade element är hela underträdet redan en hög, och ingenting behöver göras. Annars byter vi ut elementet i - med det största av dess barn, varefter vi kör Heapify för denna son .

Proceduren slutförs i tid .

Heapify( A , i ) left ← 2 i right ← 2 i +1 heap_size - antalet element i högen störst ← i om vänster ≤ A . heap_size och A [ vänster ] > A [ störst ] sedan störst ← vänster om höger ≤ A. heap_size och A [ höger ] > A [ störst ] sedan störst ← höger om störst ≠ i sedan Byt ut A [ i ] ↔ A [ störst ] Heapify( A , största )

För språk som inte stöder automatisk svansrekursionsoptimering kan implementeringseffektiviteten förbättras genom att bli av med rekursion.

Bygga en hög

Denna procedur är utformad för att skapa en hög från en oordnad uppsättning indata.

Observera att om du kör Heapify på alla element i array A, från den sista till den första, kommer det att bli en heap. Det är faktiskt lätt att bevisa genom induktion att när Heapify(A, i) exekveras, är alla underträd vars rötter har ett index som är större än i högar, och därför, efter att Heapify(A, i) exekveras, alla underträd vars rötter har ett index som inte är mindre än i.

Dessutom gör Heapify(A,i) ingenting om i>N/2 (vid numrering från det första elementet), där N är antalet arrayelement. Sådana element har faktiskt inga barn, därför är motsvarande underträd redan högar, eftersom de bara innehåller ett element.

Det räcker alltså att anropa Heapify för alla element i array A, med början (när man numrerar från det första elementet) från -th och slutar med det första.

Build_Heap( A ) A . heap_size ← A . längd för i ← ⌊ A . längd /2⌋ ner till 1 gör Heapify( A , i )

Även om det finns n/2 anrop till Heapify-funktionen här med komplexitet , kan det visas att körtiden är [1] .

Hög sortering

Heapsort-proceduren sorterar en array utan att använda ytterligare minne i tid .

För att förstå dess funktion kan vi föreställa oss att vi har bytt ut det första elementet (det vill säga roten) med det sista. Då blir det sista elementet det största. Om vi ​​efter det utesluter det sista elementet från högen (det vill säga formellt minska dess längd med 1), kommer de första N-1 elementen att uppfylla alla villkoren för högen, utom kanske roten. Om du anropar Heapify kommer de första N-1 elementen att bli en heap, och de sista kommer att vara större än alla. Genom att upprepa dessa steg N-1 gånger kommer vi att sortera arrayen.

Heapsort ( A ) Build_Heap( A ) för i ← A . längd ner till 1 do Byt A [1] ↔ A [ i ] A . heap_size ← A . heap_size -1 Heapify( A ,1)

Ändra värdet på ett element

Heap_Increase_Key-proceduren ersätter ett heapelement med en ny nyckel med ett värde som är större än eller lika med värdet på det ursprungliga elementet . Vanligtvis används denna procedur för att lägga till ett godtyckligt element till högen. Tidskomplexitet .

Om elementet är mindre än dess överordnade, är villkor 1 uppfyllt för hela trädet, och inget annat behöver göras. Är han större byter vi plats med hans pappa. Om pappan efter det är större än farfar så byter vi pappan med farfar osv. Med andra ord, ett för stort element flyter till toppen.

Heap_Increase_Key( A , i , key ) om tangent < A [ i ] då felet "Den nya nyckeln är mindre än den föregående" A [ i ] ← tangent medan i > 1 och A [⌊ i /2⌋] < A [ i ] gör Byt A [ i ] ↔ A [⌊ i /2⌋] i ← ⌊ i /2⌋

I det fall det är nödvändigt att minska värdet på ett element kan du anropa Heapify.

Lägga till ett element

Utför att lägga till ett element i högen i tid .

Lägga till ett godtyckligt element i slutet av högen och återställa orderegenskapen 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)

Extrahera det maximala elementet

Hämtar det maximala elementet från högen i tid .

Extraktion utförs i fyra steg:

Heap_Extract_Max( A ) om A . heap_size [ A ] < 1 sedan felet "Högen är tom" max ← A [1] A [1] ← A [ A .heap_size] A . heap_size ← A . heap_size -1 Heapify( A , 1) return max

Se även

Länkar

  1. ↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 6. Heapsort // Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - S. 178 - 193. - ISBN 5-8459-0857-4 .

Kommentarer

  1. ↑ Om sorteringsordningen är omvänd, får värdet vid någon nod inte vara större än värdena för dess avkomlingar.
 Data struktur
Listor
Träd
Räknar
Övrig