Heapify All The Things With Heap Sort

Vaidehi Joshi

Follow

Iulie 13, 2017 – 11 min citește

Cineva mi-a spus odată că tot ce este important în informatică se reduce la copaci. La propriu, doar copaci. Îi putem folosi pentru a construi lucruri, pentru a analiza lucruri și pentru a interpreta lucruri (da, s-ar putea să se întâmple ceva prefigurări aici, nu vă faceți griji dacă încă nu are niciun sens pentru voi, pentru că în curând va avea!) Și le putem folosi chiar și pentru a – ați ghicit! – să sortăm lucrurile.

Ah, sortarea. Am făcut atât de multe în ultimele săptămâni, dar acum ne apropiem de finalul aventurilor noastre de sortare. Cu toate acestea, este imposibil și nedrept să vorbim despre sortare fără să vorbim despre un tip special de sortare care folosește cea mai nouă structură de date din centura noastră de instrumente de structură de date.

Am învățat recent să iubim heaps, un tip special de arbore binar care urmează un set strict de reguli și care sunt folosite pentru a implementa lucruri precum cozile de așteptare cu prioritate și lucrările în fundal. Dar acestea nu sunt singurele lucruri la care sunt bune heaps. Se pare că grămezile binare sunt adesea folosite doar pentru o sortare eficientă. Multe programe se bazează pe sortarea heap, deoarece se întâmplă să fie una dintre cele mai eficiente modalități de sortare a unui array. Și acum că știm ce este un heap, putem încerca să înțelegem de ce funcționează atât de bine atunci când vine vorba de problema sortării!

Înainte de a ne scufunda în heap sort, să ne asigurăm că avem heap-urile clare în cap. Ne-am putea aminti că un heap nu este de fapt nimic mai mult decât un arbore binar cu câteva reguli suplimentare pe care trebuie să le respecte: în primul rând, trebuie să aibă întotdeauna o structură de heap, în care toate nivelurile arborelui binar sunt completate, de la stânga la dreapta, și în al doilea rând, trebuie să fie ordonat fie ca un heap maxim, fie ca un heap minim. În scopul sortării heap, vom avea de-a face exclusiv cu heap-uri max, în care fiecare nod părinte (inclusiv rădăcina) este mai mare sau egal cu valoarea nodurilor sale copii.

Bine, să trecem la răspunsul la întrebarea momentului: cum sortăm folosind heap-uri? Ei bine, pentru a răspunde la această întrebare, va trebui să înțelegem mai întâi ce este un algoritm de sortare heap!

Un algoritm de sortare heap este o tehnică de sortare care se bazează pe structuri de date heap binare. Deoarece știm că heap-urile trebuie să urmeze întotdeauna o anumită ordine, putem profita de această proprietate și o putem folosi pentru a găsi cel mai mare element, elementul cu valoare maximă, și pentru a sorta secvențial elementele prin selectarea nodului rădăcină al unui heap și adăugarea acestuia la sfârșitul tabloului.

Știm deja că sortarea heap este o modalitate eficientă de sortare a unui tablou nesortat; dar ce are de-a face un tablou cu un heap? Și cum sortăm un tablou folosind un heap? Ei bine, există trei pași cheie pentru modul în care acest lucru funcționează în practică. Le vom examina mai în profunzime într-un moment, dar să aruncăm mai întâi o privire de nivel înalt asupra a ceea ce sunt acești trei pași.

1. Pentru început, avem un tablou nesortat. Primul pas este să luăm acel array și să îl transformăm într-un heap; în cazul nostru, vom dori să îl transformăm într-un heap maxim. Așadar, trebuie să transformăm și să construim un max heap din datele tabloului nostru nesortat. De obicei, acest lucru este încapsulat de o singură funcție, care ar putea fi numită ceva de genul buildMaxHeap.
2. După ce avem datele tabloului nostru într-un format max heap, putem fi siguri că cea mai mare valoare se află în nodul rădăcină al heap-ului. Amintiți-vă că, chiar dacă întregul heap nu va fi sortat, dacă am construit max heap-ul nostru corect și fără greșeli, fiecare nod părinte din heap-ul nostru va avea o valoare mai mare decât copiii săi. Așadar, vom muta cea mai mare valoare – aflată în nodul rădăcină – la sfârșitul heap-ului, schimbând-o cu ultimul element.
3. Acum, cel mai mare element din heap se află în ultimul nod, ceea ce este minunat. Știm că se află în poziția sa de sortare, deci poate fi eliminat complet din heap. Dar, mai este încă un pas: să ne asigurăm că noul element din nodul rădăcină se află în locul corect! Este foarte puțin probabil ca elementul pe care l-am schimbat în poziția nodului rădăcină să se afle în locația corectă, așa că vom deplasa elementul nodului rădăcină în jos, până la locul corect, folosind o funcție care se numește de obicei ceva de genul heapify.

Și asta este practic tot! Algoritmul continuă să repete acești pași până când heap-ul este redus la un singur nod. În acel moment, acesta știe că toate elementele din tabloul nesortat sunt în pozițiile lor sortate și că ultimul nod rămas va sfârși prin a fi primul element din tabloul sortat.

Bine, știu că am spus că aceștia sunt singurii trei pași pentru sortarea grămezii. Dar dacă acești trei pași vi se par confuzi, nu vă faceți griji; ei pot fi destul de complicați și greu de înțeles până când îi vedeți în acțiune. De fapt, cred că acest algoritm are mult mai mult sens cu un exemplu ilustrat. Deoarece grămezile sunt un tip de arbore, este util să le vizualizăm, la fel cum facem cu arborii binari. Așa că haideți să facem asta chiar acum!

Ați privit vreodată sub capota heap sort-ului?

În regulă, este timpul pentru partea mea favorită absolută de învățare a heap sort-ului: desenarea lui! Ura! Pentru a înțelege ce se întâmplă sub capota heap sort, vom lucra cu un mic set de date nesortate.

Vom începe cu un array nesortat cu cinci elemente care sunt super dezordonate: .

Amintiți-vă că, din moment ce lucrăm cu sortarea heap, va trebui să transformăm această matrice într-un heap, pentru început.

În ilustrația prezentată aici, puteți vedea că matricea a fost transformată într-un copac – nu este încă un heap pentru că nu este încă în nici o ordine maximă sau minimă! Putem observa acest lucru deoarece 3 nu este nici cel mai mare, nici cel mai mic element și, totuși, este nodul rădăcină în acest moment. Acesta este doar un arbore, cu elementele din matrice transpuse direct în formatul unui arbore binar.

Dar, din moment ce trebuie să avem de-a face cu un max heap, va trebui să transformăm structura noastră dintr-un arbore binar într-un max heap. Observați cum, în max heap, nodurile părinte sunt toate mai mari decât copiii lor. Săptămâna trecută, am învățat algoritmii care ne permit să determinăm nodurile copil din indexul unei matrice; săptămâna aceasta, îi vedem în acțiune. Acești algoritmi sunt cei pe care îi folosim pentru a transforma această matrice într-un arbore și apoi într-un heap.

Bine, acum avem un max heap real. Grozav! Acum trecem la munca propriu-zisă de sortare.

Din moment ce știm că cel mai mare element se află în nodul rădăcină, știm că va trebui să-l punem chiar la capătul array-ului, în ultimul loc de indexare disponibil. Așadar, vom schimba nodul rădăcină cu ultimul nod. Odată ce facem acest schimb, ultimul nostru nod va conține cel mai mare element, cu valoare maximă.

Chiar! Acum putem vedea că 19, cel mai mare element, care înainte era nodul rădăcină, se află acum pe ultima poziție în matrice. Și, din moment ce este efectiv „sortat” în raport cu restul elementelor, îl putem elimina complet din grămadă.

Acum, vestea bună este că avem cu un nod mai puțin în grămada noastră de sortat! Vestea proastă? Grămada noastră nu mai este de fapt o grămadă: încalcă total regula de ordine a grămezii, deoarece nu este o grămadă maximă. Observați că 1 este nodul rădăcină, dar cu siguranță nu este mai mare decât cele două noduri copii ale sale, 14 și 7. Așadar, va trebui să-l mutăm în jos, la locul său corect în arbore.

Să heatificăm acest arbore și să-l facem din nou un heap maxim!

Frumos! În ilustrația de mai sus, putem vedea că mai întâi am schimbat 1 și 14, iar apoi am schimbat 1 și 8. Acum, ne-am întors la o grămadă maximă corectă. Putem repeta aceiași pași pe care i-am făcut la sortarea elementului 19:

→ Mai întâi vom schimba primul și ultimul nod.
→ Apoi, vom suprapune arborele până când va fi din nou un max heap corespunzător.

Să facem asta cu noul nostru nod rădăcină, elementul 14. Iată cum ar arăta următorii noștri doi pași:

Rad! Am schimbat primul și ultimul nod, iar apoi am eliminat ultimul nod, 14, deoarece se afla în poziția de sortare. Singurul lucru pe care trebuia să îl facem în continuare era să mutăm nodul rădăcină în locația sa corectă și să suprapunem elementul 3 până când am revenit la o stare de heap maximă.

Am continua să facem acest lucru de încă trei ori. În cele din urmă, am fi rămas doar cu 1, ultimul nod din heap. În acest moment, algoritmul de sortare a grămezii ar fi terminat și am ști că 1 ar fi primul element din tablou și am ști că tabloul a fost în sfârșit sortat.

Iată o vizualizare excelentă a întregului proces pe care tocmai l-am parcurs. Observați cum, cu fiecare sortare iterativă, cel mai mare element nesortat ajunge la locul său corect în heap, și apoi în array.

Heap sort: la ce este bun?

Când am citit pentru prima dată despre heap sort, ceva despre algoritmul acesta mi s-a părut ciudat de familiar. Abia după ce am ilustrat heap sort mi-am dat seama de unde venea senzația mea de déjà vu: heap sort era aproape exact ca selection sort! Poate vă amintiți de la începutul seriei că selection sort este un algoritm de sortare care sortează o listă de elemente nesortate prin iterarea unei liste de elemente, găsirea celui mai mic și punerea lui deoparte într-o listă sortată. Continuă să sorteze găsind cel mai mic element nesortat și adăugându-l la lista sortată.

Nu sună foarte asemănător cu sortarea în grămadă, dar inversat?

Se pare că heap sort seamănă foarte mult cu selection sort în logica sa: ambii algoritmi găsesc fie cel mai mic, fie cel mai mare element, îl „selectează” și plasează acel element în locația sa corectă în lista sortată.

Cu toate acestea, oricât de asemănătoare ar fi, heap sort este mult mai bun decât selection sort într-un mod masiv: performanța sa! Heap sort este practic o versiune super-ameliorată a sortării prin selecție. Da, găsește cel mai mare element dintr-o colecție nesortată și îl ordonează la sfârșitul listei – cu toate acestea, face toată această muncă mult mai repede decât ar face-o sortarea prin selecție!

Ok, deci cât de mult mai rapidă este heap sort? Și de ce este mai rapid?

Bine, haideți să aruncăm o privire la cod. Există diverse implementări ale heap sort, iar codul de mai jos este adaptat de la implementarea JavaScript a heap sort de către Rosetta Code. Vă veți aminti că heap sort are două părți importante: buildMaxHeap și heapify. Le putem vedea în acțiune în versiunea de heapSort de mai jos.

Funcția buildMaxHeap face munca de creare efectivă a heap-ului maxim. Observați că până și această funcție apelează la heapify, care face treaba de a muta câte un element pe rând în jos, până la locația sa corectă în heap.

Funcția heapify este destul de importantă, așa că să ne uităm la ea. Observați că se bazează pe algoritmii de determinare a copilului din stânga și din dreapta al unui nod, despre care am discutat săptămâna trecută când am învățat prima dată despre heaps.

Și, nu în ultimul rând, funcția swap, pe care am mai văzut-o înainte în alți algoritmi de sortare, dar merită să ne uităm rapid pentru a ne reaminti ce face:

Bine, acum că avem un context pentru modul în care aceste funcții interacționează și se invocă unele pe altele, să ne întoarcem la întrebarea noastră inițială despre cum și de ce sortarea heap este mult mai eficientă decât sortarea prin selecție! Dacă ne uităm în profunzime la cod, vom observa două lucruri: în primul rând, trebuie să construim heap-ul maxim o singură dată, transmițându-i toate elementele tabloului; în al doilea rând, trebuie să heatificăm din nou și din nou toate elementele din heap, cu excepția primului element al nodului rădăcină.

Aceste două observații sunt, de fapt, cheia întrebării cum și de ce sortarea heap este atât de rapidă precum este. Apelarea buildMaxHeap necesită timp O(n), deoarece fiecare element trebuie adăugat la heap, iar o cantitate mai mare de elemente înseamnă un heap mai mare. Cu toate acestea, nu uitați că avem de-a face cu un arbore binar, iar arborii binari sunt de natură logaritmică. Deci, chiar dacă trebuie să apelăm heapify din nou și din nou, invocarea acestei funcții este de fapt destul de rapidă, deoarece se va executa în timp logaritmic, sau O(log n).

Combinarea acestor două complexități temporale este ceva ce am mai văzut deja înainte! Sortarea grămezii se execută în timp liniaritmic, sau în notația Big O, O(n log n). Deci, chiar dacă heap sort pare atât de asemănător cu selection sort, este mult mai rapid! Sortarea prin selecție se execută în timp pătratic, sau O(n²), ceea ce este mult mai puțin eficient decât timpul liniaritmic.

Să ne uităm rapid la celelalte moduri în care heap sort se compară cu alți algoritmi de sortare.

Heap sort transformă matricea care îi este transmisă pe măsură ce sortează; spre deosebire de unii algoritmi de sortare, acesta nu creează o copie complet separată a datelor de intrare. Acest lucru îl face să fie un algoritm de sortare in-place. De asemenea, sortarea Heap nu are nevoie de memorie externă, fiind un algoritm de sortare internă. Se execută iterativ (și, prin urmare, este non-recursiv) și compară două elemente la un moment dat, atunci când schimbă și apelează funcția heapify, ceea ce îl face un algoritm de sortare prin comparație.

Dar, din cauza naturii grămezilor și a funcției heapify, dacă există elemente duplicate, nu ne putem baza pe faptul că elementele își păstrează ordinea! Așadar, sortarea în grămadă este instabilă; acesta este un diferențiator major între sortarea combinată și sortarea în grămadă, care se bazează fiecare pe structuri de arbori pentru a funcționa atât de eficient. Cu toate acestea, merge sort câștigă în bătălia stabilității, în timp ce heap sort eșuează în această categorie.

În ciuda diferențelor dintre ele, merge sort și heap sort pot fi de acord asupra unui lucru: fără arbori binari, ambele ar fi pierdute!

Resurse

Există niște note de curs și prelegeri cu adevărat fantastice despre heap sorting, precum și câteva tutoriale video bune. Am făcut câteva căutări pe Google ca să nu trebuiască să o faceți voi! Iată câteva locuri grozave de unde puteți începe dacă sunteți interesat să aflați mai multe despre heap sort.

1. Introducere în algoritmi: Heap Sort, MIT
2. Algoritmi: Heap Sort, Profesor Ching-Chi Lin
3. Heap sort, Growing with the Web
4. Heap sort în 4 minute, Michael Sambol
5. Heap sort: Max heap, strohtennis