Structuri de Date 2023 - C4: Heap. HeapSort

Structuri de Date

Curs 4: Heap. HeapSort

Cuprins:

Heap
Reprezentarea arborilor cu array
Insertia in heap
Extragerea din heap
Heap Sort

1. Heap

Heap(ansamblu) este un arbore binar complet pe nivele.
Este e structura arborescenta reprezentata printr-un tablou(array).
In loc de pointeri, legaturile dintre nodurile parinte si fiu sunt date de pozitia elementelor in tablou(array).
Heap-ul este un arbore ordonat:
1. min-heap: parintele < ambii fii
2. max-heap: parintele > ambii fii

Min-heap:

2. Reprezentarea arborilor cu array

Pentru array-uri care incep de la pozitia 1 iar pozitia 0 este nefolosita:

fiul stang al elementului i se gaseste la pozitia 2*i

fiul drept al elementului i se gaseste la pozitia 2*i+1

tatal elementului i se gaseste la pozitia i/2

Pentru array-uri care incep de la pozitia 0:

fiul stang al elementului i se gaseste la pozitia 2*i+1

fiul drept al elementului i se gaseste la pozitia 2*i+2

tatal elementului i se gaseste la pozitia (i-1)/2

Avantaje:

Economisim multa memorie pentru ca nu mai stocam pointeri.
Avem la dispozitie imediat si legatura catre parintele unui nod fara a fi nevoie de un pointer suplimentar.
Nu mai e nevoie sa facem management-ul pointerilor.

Dezavantaje:

Mai putin "dinamic" decat arborele cu pointeri pentru ca trebuie realocat array-ul in momentul depasirii dimensiunii maxime.
Nu putem sa reprezentam decat arbori binari completi pe nivele, sau arbori cat mai asemanatori cu acestia. Un arbore degenerat nu se poate reprezenta eficient cu array!
Inserarea sau Eliminarea unui element nu se poate face decat de la final pentru a mentine proprietatea complet-pe-nivele.

3. Insertia in heap

Heap-ul este un arbore ordonat:
1. min-heap: parintele < ambii fii

Insertia unei valori in min-heap trebuie sa respecte doua conditii:

sa pastreze structura de arbore complet pe nivele
sa pastreze proprietatea parinte<fiu

Insertie Heap

Pentru a realiza insertia in min-heap:

noul element se insereaza pe ultima pozitie din array, dimensiunea heap-ului creste cu 1,
elementul se propaga in sus prin interschimbari pana cand este verificata conditia parinte<fiu
sau pana cand elementul ajunge in radacina (deci era cel mai mic din toate elementele din heap)

//min heap indexat de la 0struct min_heap{ int h[200]; int n=0; void insert_heap(int x){ h[n]=x; n++; int index=n-1; while (index>0 && h[(index-1)/2]>h[index]){//tatal in ordine incorecta swap(h[(index-1)/2],h[index]); index = (index-1)/2; // mergem in sus sa reparam heap } }};

4. Extragerea din heap

Extragerea radacinii (valoarea minima) din min-heap trebuie sa respecte doua conditii:

sa pastreze structura de arbore complet pe nivele
sa pastreze proprietatea parinte<fiu

Extragere Heap

Pentru a realiza extragerea radacinii din min-heap:

radacina face swap pe ultima pozitie din array, dimensiunea heap-ului scade cu 1,
elementul din radacina se propaga in jos prin interschimbari pana cand este verificata conditia parinte<fiu
sau pana cand elementul nu mai are fii

//min heap indexat de la 0struct min_heap{ int h[200]; int n=0; int extract_heap(){ swap(h[0],h[n-1]); n--; int index=0,ok=0; do{ ok=0; int index_element_minim=index; //daca exista fiu stang si e mai mic if (index*2+1<n && h[index*2+1]<h[index]) index_element_minim=index*2+1;//minimul de pana acum este fiu stang //daca exista fiu drept si e mai mic if (index*2+2<n && h[index*2+2]<h[index_element_minim]) index_element_minim=index*2+2;//minimul de pana acum este fiu drept //daca parintele nu e cel mai mic if (index_element_minim!=index){ ok=1; swap(h[index],h[index_element_minim]); index=index_element_minim; } } while(ok); return h[n]; }};

5. Heap Sort

Pentru a sorta cu heapsort:

Construim un heap cu valorile pe care le dorim sortate.
- Min-heap pentru a sorta descrescator
- Max-heap pentru a sorta crescator
Extragem radacina de n-1 ori si o punem la final.

#include <iostream>using namespace std; struct min_heap{ int h[200]; int n=0; void insert_heap(int x){ h[n]=x; n++; int index=n-1; //while tatal in ordine incorecta while (index>0 && h[(index-1)/2]>h[index]){ swap(h[(index-1)/2],h[index]); index = (index-1)/2; // mergem in sus sa reparam heap } } int extract_heap(){ swap(h[0],h[n-1]); n--; int index=0; int ok=0; do{ ok=0; int index_element_minim=index; //daca exista fiu stang si e mai mic if (index*2+1<n && h[index*2+1]<h[index]) index_element_minim=index*2+1; //minimul de pana acum este fiu stang //daca exista fiu drept si e mai mic if (index*2+2<n && h[index*2+2]<h[index_element_minim]) index_element_minim=index*2+2; //minimul de pana acum este fiu drept if (index_element_minim!=index){ ok=1; swap(h[index],h[index_element_minim]); index=index_element_minim; } } while(ok); return h[n]; } int heapsort(){ int N=n; while (n>0) extract_heap(); return N; }};

int main(){ min_heap H; H.insert_heap(2); H.insert_heap(4); H.insert_heap(3); H.insert_heap(5); H.insert_heap(9); H.insert_heap(8); H.insert_heap(6); H.insert_heap(7); H.insert_heap(8);
int N=H.heapsort(); for (int i=0;i<N;i++) cout<<H.h[i]; return 0;}

HeapSort

Complexitate

Complexitate Heap

Insertia in heap, average = worst: O( log n )

Extragerea radacinii, average = worst: O( log n )

Complexitate HeapSort

Constructia heapului prin n insertii : O( n log n )

Extragerea radacinii de n ori: O( n log n )

Total: O( n log n ) + O( n log n ) = O( n log n )