Morman binar

Un hap binar , o piramidă [1] sau un arbore de sortare este un arbore binar care îndeplinește trei condiții:

Valoarea la orice vârf nu este mai mică decât valorile descendenților săi [K 1] .
Adâncimea tuturor frunzelor (distanța până la rădăcină) diferă cu cel mult 1 strat.
Ultimul strat este umplut de la stânga la dreapta fără „găuri”.

Există, de asemenea, grămezi în care valoarea la orice vârf, dimpotrivă, nu este mai mare decât valorile descendenților săi. Astfel de grămezi se numesc min-heap, iar grămada descrise mai sus se numește max-heap. În cele ce urmează, se ia în considerare numai max-heap. Toate acțiunile cu min-heap sunt efectuate în mod similar.

O structură de date convenabilă pentru un arbore de sortare este o matrice A , al cărei prim element, A [1] este elementul de la rădăcină, iar copiii elementului A [ i ] sunt A [2 i ] și A [2 i +1 ] (la numerotarea elementelor cu primul). La numerotarea elementelor de la zero, elementul rădăcină este A [0], iar copiii elementului A [ i ] sunt A [2 i +1] și A [2 i +2]. Cu această metodă de depozitare, condițiile 2 și 3 sunt îndeplinite automat.

Înălțimea mormanului este definită ca înălțimea arborelui binar. Adică, este egal cu numărul de margini din calea cea mai lungă simplă care leagă rădăcina mormanei cu una dintre frunzele sale. Înălțimea heap-ului este , unde N este numărul de noduri de arbore. $\Theta \left(\log {N}\dreapta)$

Funcționalitate

Puteți efectua următoarele operații pe un heap:

Adăugați un element la heap. Complexitate $O(\log{n})$
Scoateți elementul maxim din grămada. Ore de lucru $O(\log{n})$
Schimbați valoarea oricărui element. Ore de lucru $O(\log{n})$

Pe baza acestor operații, puteți efectua următoarele acțiuni:

Transformați o matrice neordonată de elemente într-un heap. Complexitate $Pe)$
Sortați o matrice transformând-o într-un heap și heap-ul într-o matrice sortată. Ore de lucru $O(n\log{n})$

Iată numărul de elemente heap. Complexitatea spațiului - pentru toate operațiunile și acțiunile de mai sus. $n$ $O(1)$

O descriere detaliată și algoritmi ai acestor acțiuni și procedura Heapify necesară pentru a le efectua sunt date în secțiunea următoare.

Proceduri de bază

Această secțiune prezintă procedurile de bază pentru lucrul cu un heap.

Restaurarea proprietăților heap

Dacă unul dintre elementele din heap se modifică, atunci este posibil să nu mai satisfacă proprietatea de ordonare. Pentru a restabili această proprietate, utilizați procedura Heapify. Restaurează proprietatea heap într-un arbore ale cărui subarbori din stânga și din dreapta o satisfac. Această procedură ia ca intrare un tablou de elemente A și index i . Restabilește proprietatea de ordonare în întregul subarboresc a cărui rădăcină este elementul A [ i ].

Dacă elementul i --lea este mai mare decât copiii săi, întregul subarbore este deja o grămadă și nu trebuie făcut nimic. În caz contrar, schimbăm elementul i --lea cu cel mai mare dintre copiii săi, după care executăm Heapify pentru acest fiu.

Procedura este finalizată la timp . $O\stânga(\log {n}\dreapta)$

Heapify( A , i ) left ← 2 i right ← 2 i +1 heap_size - numărul de elemente din heap cel mai mare ← i dacă stânga ≤ A . heap_size și A [ stânga ] > A [ mai mare ] apoi cea mai mare ← stânga dacă dreapta ≤ A. heap_size și A [ dreapta ] > A [ cea mai mare ] apoi cea mai mare ← dreapta dacă cea mai mare ≠ i atunci Schimbați A [ i ] ↔ A [ cea mai mare ] Heapify( A , cel mai mare )

Pentru limbile care nu acceptă optimizarea automată a recursiunii de coadă , eficiența implementării poate fi îmbunătățită prin eliminarea recursiunii.

Construirea unui morman

Această procedură este concepută pentru a crea un heap dintr-o matrice neordonată de date de intrare.

Rețineți că dacă executați Heapify pe toate elementele matricei A, de la ultimul până la primul, acesta va deveni un heap. Într-adevăr, este ușor de demonstrat prin inducție că, în momentul în care Heapify(A, i) este executat, toți subarborele ale căror rădăcini au un indice mai mare decât i sunt grămezi și, prin urmare, după ce Heapify(A, i) este executat, toți subarbori ale căror rădăcini au un indice nu mai mic decât i.

De asemenea, Heapify(A,i) nu face nimic dacă i>N/2 (la numerotarea de la primul element), unde N este numărul de elemente ale matricei. Într-adevăr, astfel de elemente nu au copii, prin urmare subarborele corespunzătoare sunt deja grămezi, deoarece conțin un singur element.

Astfel, este suficient să apelăm Heapify pentru toate elementele matricei A, începând (la numerotarea de la primul element) de la --lea și terminând cu primul. $[N/2]$

Build_Heap( A ) A . heap_size ← A . lungime pentru i ← ⌊ A . lungime /2⌋ până la 1 face Heapify( A , i )

Deși există n/2 apeluri la funcția Heapify aici cu complexitate , se poate demonstra că timpul de rulare este [1] . $O\stânga(\log {n}\dreapta)$ $Pe)$

Sortare heap

Procedura Heapsort sortează o matrice fără a utiliza memorie suplimentară în timp . $O\stânga(n\log {n}\dreapta)$

Pentru a înțelege funcționarea acestuia, ne putem imagina că am schimbat primul element (adică rădăcina) cu ultimul. Apoi ultimul element va fi cel mai mare. Dacă după aceea excludem ultimul element din heap (adică îi reducem în mod formal lungimea cu 1), primele N-1 elemente vor îndeplini toate condițiile heap-ului, cu excepția poate rădăcinii. Dacă apelați Heapify, primele elemente N-1 vor deveni o grămadă, iar ultimele vor fi mai mari decât toate. Repetând acești pași de N-1 ori, vom sorta matricea.

Heapsort ( A ) Build_Heap( A ) for i ← A . lungime până la 1 face Swap A [1] ↔ A [ i ] A . heap_size ← A . heap_size -1 Heapify( A ,1)

Modificarea valorii unui element

Procedura Heap_Increase_Key înlocuiește un element heap cu o nouă cheie cu o valoare mai mare sau egală cu valoarea elementului original . De obicei, această procedură este utilizată pentru a adăuga un element arbitrar la heap. Complexitatea timpului . $O\stânga(\log {n}\dreapta)$

Dacă elementul este mai mic decât părintele său, condiția 1 este îndeplinită pentru întregul arbore și nu trebuie făcut nimic altceva. Dacă este mai mare, schimbăm locurile cu tatăl lui. Dacă după aceea tatăl este mai mare decât bunicul, schimbăm tatăl cu bunicul și așa mai departe. Cu alte cuvinte, un element prea mare plutește în vârf.

Heap_Increase_Key( A , i , key ) if key < A [ i ] then error "Noua cheie este mai mică decât cea anterioară" Tasta A [ i ] ← în timp ce i > 1 și A [⌊ i /2⌋] < A [ i ] fac Schimbați A [ i ] ↔ A [⌊ i /2⌋] i ← ⌊ i /2⌋

În cazul în care este necesară reducerea valorii unui element, puteți apela Heapify.

Adăugarea unui element

Efectuează adăugarea unui element la heap în timp . $O\stânga(\log {n}\dreapta)$

Adăugarea unui element arbitrar la sfârșitul heap-ului și restaurarea proprietății de ordine cu Heap_Increase_Key.

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

Extragerea elementului maxim

Preia în timp elementul maxim din heap . $O\stânga(\log {n}\dreapta)$

Extragerea se realizează în patru etape:

valoarea elementului rădăcină (este cea maximă) este stocată pentru returnare ulterioară
ultimul element este copiat în rădăcină și apoi eliminat din heap
numit Heapify pe rădăcină
elementul stocat este returnat

Heap_Extract_Max( A ) dacă A . heap_size [ A ] < 1 apoi eroare „Heap is empty” max ← A [1] A [1] ← A [ A .heap_size] A . heap_size ← A . heap_size -1 Heapify( A , 1) return max

Vezi și

Link -uri

↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capitolul 6. Heapsort // Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - S. 178 - 193. - ISBN 5-8459-0857-4 .

Comentarii

↑ Dacă ordinea de sortare este inversată, atunci valoarea oricărui nod nu trebuie să fie mai mare decât valorile descendenților săi.

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree