Un heap este denumit „parțial ordonat” și nu „parțial sortat”. Cuvântul „sortare” înseamnă ordonare completă (sortare completă). Un heap nu este parțial ordonat în mod arbitrar. Un heap este parțial ordonat după un criteriu (model), așa cum se arată mai jos.
Deci, heapsort constă din două etape: construirea heap-ului și extragerea elementului ordonat din partea de sus a heap-ului. În a doua etapă, după fiecare extracție, grămada este reconstruită. Fiecare reconstrucție este mai rapidă decât procesul de construcție inițial, deoarece reconstrucția se face dintr-o construcție anterioară, în care un element a fost eliminat. Și cu asta, heapsort sortează o listă complet nesortată.
Scopul acestui articol este de a explica pe scurt heapsort și apoi de a produce complexitatea sa în timp (vezi mai jos sensul complexității timpului). Spre final, codarea se face în C++.
Heap minim
Un heap poate fi un heap minim sau maxim. Un max-heap este unul în care primul element este cel mai înalt element, iar întregul arbore sau lista corespunzătoare este parțial ordonată în ordine descrescătoare. Un min-heap este unul în care primul element este cel mai mic element, iar întreaga listă este parțial ordonată în ordine crescătoare. În acest articol, se ia în considerare doar heap-ul minim. Notă: în subiectul heap, un element este numit și nod.
O grămadă este un arbore binar complet. Arborele binar poate fi exprimat ca o matrice (listă); citeste de sus in jos si de la stanga la dreapta. Proprietatea heap pentru un min-heap este că un nod părinte este mai mic sau egal cu fiecare dintre cei doi copii ai săi. Un exemplu de listă neordonată este:
| 9 | 19 | 24 | 5 | 3 | unsprezece | 14 | 22 | 7 | 6 | 17 | cincisprezece | nul | nul | nul |
| 0 | 1 | Două | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | unsprezece | 12 | 13 | 14 |
Primul rând al acestui tabel sunt elementele matricei. În al doilea rând sunt indicii bazați pe zero. Această listă de elemente poate fi exprimată ca un arbore. Elementele nule au fost adăugate pentru a face un arbore binar complet. Strict vorbind, elementele nule nu fac parte din listă (arborele). Această listă nu are ordine, deci nu este încă o grămadă. Va deveni un heap atunci când a avut o comandă parțială, conform proprietății heap.
Relația dintre noduri și indici
Amintiți-vă, un heap este un arbore binar complet înainte de a avea configurația heap (proprietatea heap). Lista anterioară nu este încă un heap, deoarece elementele nu respectă proprietatea heap. Devine un heap după rearanjarea elementelor în ordine parțială în funcție de proprietatea min-heap. Ordinea parțială poate fi văzută ca sortare parțială (deși cuvântul „sortare” înseamnă ordonare completă).
Indiferent dacă un arbore binar este o grămadă sau nu, fiecare părinte are doi copii, cu excepția nodurilor (ultimelor) frunze. Există o relație matematică între indici dintre fiecare părinte și copiii săi. Este după cum urmează: Dacă părintele este la indexul i, atunci copilul din stânga este la index:
Două * i + 1iar copilul potrivit este la index:
Două * i + DouăAceasta este pentru indexarea pe bază de zero. Și astfel, un părinte la indicele 0 are copilul stâng la indicele 2×0+1=1 și copilul său drept la 2×0+2=2. Un părinte la indicele 1 are copilul stâng la indicele 2×1+1=3 și copilul drept la indicele 2×1+2=4; si asa mai departe.
După proprietatea min-heap, un părinte la i este mai mic sau egal cu copilul stâng la 2i+1 și mai mic sau egal cu copilul drept la 2i+2.
Morman
A îngrămădi înseamnă a construi o grămadă. Înseamnă să rearanjați elementele unei liste (sau arborelui corespunzător) astfel încât acestea să satisfacă proprietatea heap. La sfârșitul procesului de heapifying, lista sau arborele este un heap.
Dacă lista anterioară nesortată este aglomerată, aceasta va deveni:
| 3 | 5 | unsprezece | 7 | 6 | cincisprezece | 14 | 22 | 9 | 19 | 17 | 24 | nul | nul | nul |
| 0 | 1 | Două | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | unsprezece | 12 | 13 | 14 |
Notă: există 12 elemente și nu 15 în listă. Pe al doilea rând sunt indicii. În procesul de construire a grămezilor, elementele au trebuit să fie verificate, iar unele schimbate.
Observați că cel mai mic și primul element este 3. Restul elementelor urmează într-o manieră ascendentă, dar ondulată. Dacă copiii din stânga și din dreapta din pozițiile 2i+1 și 2i+2 sunt fiecare mai mare sau egal cu părintele de la i, atunci acesta este un min-heap. Aceasta nu este o comandă sau o sortare completă. Aceasta este o ordonare parțială, conform proprietății heap. De aici începe următoarea etapă pentru sortarea heap.
Heapify Time Complexity
Complexitatea timpului este timpul relativ de rulare al unui cod. Acesta poate fi văzut ca numărul de operațiuni principale pentru finalizarea acelui cod. Există diferiți algoritmi pentru construirea heap-ului. Cel mai eficient și mai rapid împarte în mod continuu lista în două, verificând elementele de jos și apoi făcând unele schimburi de elemente. Fie N numărul de elemente practice din listă. Cu acest algoritm, numărul maxim de operații principale (swapping) este N. Complexitatea timpului pentru heapifying este dată anterior ca:
O ( n )Unde n este N și este numărul maxim posibil de operații principale. Această notație se numește notația Big-O. Începe cu O în litere mari, urmată de paranteze. În paranteze se află expresia pentru cel mai mare număr posibil de operații.
Amintiți-vă: adunarea poate deveni înmulțire dacă același lucru adăugat se repetă în continuare.
Heapsort Ilustrație
Lista anterioară nesortată va fi folosită pentru a ilustra heapsort. Lista dată este:
9 19 24 5 3 unsprezece 14 22 7 6 17 cincisprezeceMin-heap-ul produs din listă este:
3 5 unsprezece 7 6 cincisprezece 14 22 9 19 17 24Prima etapă în heapsort este de a produce grămada care a fost produsă. Aceasta este o listă parțial ordonată. Nu este o listă sortată (complet sortată).
A doua etapă constă în îndepărtarea celui mai mic element, care este primul element, din heap, re-heapificarea heap-ului rămas și eliminarea celor mai puține elemente din rezultate. Cel mai mic element este întotdeauna primul element din grămada re-aglomerată. Elementele nu sunt îndepărtate și aruncate. Ele pot fi trimise într-o matrice diferită în ordinea în care sunt eliminate.
În final, noua matrice ar avea toate elementele sortate (complet), în ordine crescătoare; și nu mai este doar parțial comandat.
În a doua etapă, primul lucru de făcut este să eliminați 3 și să îl plasați în noua matrice. Rezultatele sunt:
3și
5 unsprezece 7 6 cincisprezece 14 22 9 19 17 24Elementele rămase trebuie să fie acumulate înainte ca primul element să fie extras. Mulțimea elementelor rămase poate deveni:
5 6 7 9 cincisprezece 14 22 unsprezece 19 17 24Extragerea a 5 și adăugarea la noua listă (matrice) dă rezultatele:
3 5și
6 7 9 cincisprezece 14 22 unsprezece 19 17 24Îngrădirea setului rămas ar da:
6 7 9 cincisprezece 14 22 unsprezece 19 17 24Extragerea a 6 și adăugarea la noua listă (matrice) dă rezultatele:
3 5 6și
7 9 cincisprezece 14 22 unsprezece 19 17 24Îngrădirea setului rămas ar da:
7 9 unsprezece 14 22 cincisprezece 19 17 24Extragerea lui 7 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7și
9 unsprezece 14 22 cincisprezece 19 17 24Îngrădirea setului rămas dă:
9 unsprezece 14 22 cincisprezece 19 17 24Extragerea 9 și adăugarea la noua listă dă rezultatele:
3 5 6 7 9și
unsprezece 14 22 cincisprezece 19 17 24Îngrădirea setului rămas dă:
unsprezece 14 17 cincisprezece 19 22 24Extragerea 11 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezeceși
14 17 cincisprezece 19 22 24Îngrădirea setului rămas ar da:
14 17 cincisprezece 19 22 24Extragerea 14 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14și
17 cincisprezece 19 22 24Îngrădirea setului rămas ar da:
cincisprezece 17 19 22 24Extragerea a 15 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14 cincisprezeceși
17 19 22 24Îngrădirea setului rămas ar da:
17 19 22 24Extragerea 17 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14 cincisprezece 17și
19 22 24Îngrădirea setului rămas ar da:
19 22 24Extragerea 19 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14 cincisprezece 17 19și
22 24Îngrădirea setului rămas dă:
22 24Extragerea 22 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14 cincisprezece 17 19 22și
24Îngrădirea setului rămas dă:
24Extragerea 24 și adăugarea lui la noua listă oferă rezultatele:
3 5 6 7 9 unsprezece 14 cincisprezece 17 19 22 24și
- - -Matricea heap este acum goală. Toate elementele pe care le avea la început sunt acum în noua matrice (listă) și sortate.
Algoritmul Heapsort
Deși cititorul ar fi putut citi în manuale că heapsort constă din două etape, heapsort poate fi totuși văzut ca constând dintr-o etapă, care se micșorează iterativ din matricea dată. Cu aceasta, algoritmul de sortare cu heapsort este următorul:
- Măriți lista nesortată.
- Extrageți primul element din heap și puneți-l ca prim element al noii liste.
- Măriți lista rămasă.
- Extrageți primul element din noul heap și puneți-l ca element următor al noii liste.
- Repetați pașii anteriori în ordine până când lista heap este goală. La final, noua listă este sortată.
Heapsort Time Complexity Proper
Abordarea într-o etapă este utilizată pentru a determina complexitatea timpului pentru heapsort. Să presupunem că există 8 elemente nesortate de sortat.
Numărul maxim posibil de operațiuni pentru a acumula 8 elemente este 8 .The numărul maxim posibil de operațiuni pentru a îngrămădi restul 7 elemente este 7 .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul 6 elemente este 6 .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul 5 elemente este 5 .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul 4 elemente este 4 .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul 3 elemente este 3 .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul Două elemente este Două .
The numărul maxim posibil de operațiuni pentru a îngrămădi restul 1 elementul este 1 .
Numărul maxim posibil de operații este:
8 + 7 + 6 + 5 + 4 + 3 + Două + 1 = 36Media acestor numere de operațiuni este:
36 / 8 = 4.5Observați că ultimele patru grămezi din ilustrația anterioară nu s-au schimbat, când primul element a fost eliminat. Unele dintre grămezile anterioare nu s-au schimbat nici atunci când primul element a fost eliminat. Cu asta, un număr mediu mai bun de operațiuni principale (swappings) este 3 și nu 4,5. Deci, un număr mediu total mai bun de operațiuni principale este:
24 = 8 X 3=> 24 = 8 X Buturuga < sub > Două < / sub > 8
din moment ce log Două 8 = 3.
În general, complexitatea medie a timpului de caz pentru heapsort este:
O ( n. log2n )Acolo unde punctul înseamnă înmulțire și n este N, numărul total de elemente din listă (fiecare listă).
Rețineți că operația de extragere a primului element a fost ignorată. Pe tema complexității timpului, operațiunile care durează timp relativ scurt sunt ignorate.
Codare în C++
În biblioteca de algoritmi a C++, există o funcție make_heap(). Sintaxa este:
șablon < clasă RandomAccessIterator, clasă Comparaţie >constexpr gol face_grămadă ( RandomAccessIterator primul, RandomAccessIterator ultimul, Compare comp ) ;
Acesta ia iteratorul care indică primul element al unui vector ca prim argument și apoi iteratorul care indică chiar dincolo de sfârșitul vectorului ca ultimul argument. Pentru lista anterioară nesortată, sintaxa ar fi utilizată după cum urmează pentru a obține un heap minim:
vector < int > vtr = { 9 , 19 , 24 , 5 , 3 , unsprezece , 14 , 22 , 7 , 6 , 17 , cincisprezece } ;vector < int > :: iterator iterB = vtr. ÎNCEPE ( ) ;
vector < int > :: iterator iterE = vtr. Sfârşit ( ) ;
face_grămadă ( iterB, iterE, mai mare < int > ( ) ) ;
Acest cod schimbă un conținut vectorial într-o configurație minimă de heap. În următorii vectori C++, doi vectori vor fi folosiți în loc de două tablouri.
Pentru a copia și returna primul element al unui vector, utilizați sintaxa vectorială:
constexpr front de referință ( ) ;Pentru a elimina primul element al unui vector și a-l arunca, utilizați sintaxa vectorială:
constexpr ștergerea iteratorului ( poziţia const_iterator )Pentru a adăuga un element în spatele unui vector (element următor), utilizați sintaxa vectorială:
constexpr gol împinge înapoi ( const T & X ) ;Începutul programului este:
#include#include
#include
folosind spatiu de nume std ;
Sunt incluse bibliotecile de algoritm și vectori. Următoarea în program este funcția heapsort(), care este:
gol heapsort ( vector < int > & vechiV, vector < int > & nouV ) {dacă ( vechiV. mărimea ( ) > 0 ) {
vector < int > :: iterator iterB = vechiV. ÎNCEPE ( ) ;
vector < int > :: iterator iterE = vechiV. Sfârşit ( ) ;
face_grămadă ( iterB, iterE, mai mare < int > ( ) ) ;
int Următorul = vechiV. față ( ) ;
vechiV. şterge ( iterB ) ;
nouV. împinge înapoi ( Următorul ) ;
heapsort ( vechiV, nouV ) ;
}
}
Este o funcție recursivă. Utilizează funcția make_heap() a bibliotecii de algoritmi C++. Al doilea segment de cod din definiția funcției extrage primul element din vectorul vechi după construirea heap-ului și adaugă ca element următor pentru noul vector. Rețineți că în definiția funcției, parametrii vectoriali sunt referințe, în timp ce funcția este apelată cu identificatorii (numele).
O funcție principală C++ potrivită pentru aceasta este:
int principal ( int argc, char ** argv ){
vector < int > vechiV = { 9 , 19 , 24 , 5 , 3 , unsprezece , 14 , 22 , 7 , 6 , 17 , cincisprezece } ;
vector < int > nouV ;
heapsort ( vechiV, nouV ) ;
pentru ( int i = 0 ; i < nouV. mărimea ( ) ; i ++ ) {
cout << nouV [ i ] << ' ' ;
}
cout << endl ;
întoarcere 0 ;
}
Ieșirea este:
3 5 6 7 9 unsprezece 14 cincisprezece 17 19 22 24sortat (complet).
Concluzie
Articolul a discutat în detaliu natura și funcția Heap Sort, cunoscută în mod obișnuit ca Heapsort, ca algoritm de sortare. Heapify Time Complexity, Heapsort illustration și Heapsort ca algoritm au fost acoperite și susținute de exemple. Complexitatea timpului mediu pentru un program heapsort bine scris este O(nlog(n))