HeapSort

Sortarea cu ansamble HeapSort

Informaţii generale:

În dorinţa de a îmbunătăţi algoritmul sortării pin selecţie (elementul minim/maxim din vector se va aşeza in locul primului/ultimului element al vectorului, algoritmul reluându-se pentru cele n-1 elemente rămase), se pot face următoarele observaţii:

- fiecare algoritm de căutare a minimului/maximului dintre n elemente, bazat pe compararea perechilor de elemente, trebuie să facă cel puţin n-1 comparaţii (altfel, ar rămâne elemente necomparate);

- observaţia anterioară se poate aplica doar primei etape de căutare, ulterior putând folosi informaţii deja dobândite (exemplu: pentru căutarea maximului din şirul 503, 87, 512, 61, 908, 170, 897, 275, putem împărţi şirul în patru subşiruri şi să determinăm maximul din fiecare subşir: 503, 87 →503, apoi din 512, 61→521, din 908, 170→908, şi 897, 275→897, apoi comparând doar elementele 503, 521, 908, 897 vom determina maximul total, 908. Pentru a determina următorul maxim este suficient să îl căutăm printre elementele rămase 503, 521, 897, alături de 170 din grupul maximului anterior, reducând o serie de comparaţii. Deci va fi 897, apoi alegem dintre 503, 521, 170, 275, etc. ).

Şirul valorilor anterioare poate fi organizat, după cum am observat şi în exemplu, într-un arbore binar complet, pe nivelurile superioare aşezând maximul a câte 2 valori ale nivelului anterior, rădăcină ajungând maximul şirului. În etapa următoare, se înlocuieşte maximul găsit anterior cu o valoare foarte mică, astfel încât printr-un algoritm asemănător să obţinem maximul valorilor rămase, etc.

Pentru orice n se poate construi arborele binar complet cu n noduri terminale.

Un vector x cu n componente poate fi interpretat ca un arbore binar. Mecanismul este următorul:

rădăcina este etichetată cu x[1];
nodul etichetat cu x[i] subordonează:
- la stânga nodul etichetat cu x[2*i], dacă 2*i≤n;
- la dreapta nodul etichetat cu x[2*i+1], dacă 2*i+1≤n.

Exemplu: Arborele binar complet asociat vectorului x: 5, 8, 2, 1, 9, 4, 3, 7, 6.

i	1	2	3	4	5	6	7	8	9
x[i]	5	8	2	1	9	4	3	7	6

8 ----- 2

1 ------ 9 4----- 3

7 ----- 6

Definiţie: Un MinHeap este un arbore binar complet cu proprietăţile:

- informaţiile din noduri sunt valori dintr-o mulţime total ordonată, numite chei;

- pentru orice nod x[i], cheia memorată în x[i] este mai mică sau egală cu cheia oricăruia dintre fii.

-oricare ar fi i din mulţimea de indici{1, ... , [n/2]}, atunci x[i]<=x[2*i] şi x[i]<=x[2*i+1], dacă 2*i+1<=n

Definiţie: Un MaxHeap este un arbore binar complet cu proprietăţile:

- informaţiile din noduri sunt valori dintr-o mulţime total ordonată, numite chei;

- pentru orice nod x[i], cheia memorată în x[i] este mai mare sau egală cu cheia oricăruia dintre fii.

-oricare ar fi i din mulţimea de indici{1, ... , [n/2]}, atunci x[i]>=x[2*i] şi x[i]>=x[2*i+1], dacă 2*i+1<=n

Observaţie: În cazul arborelui reprezentat pentru un vector de tip MinHeap, orice nod subordonează noduri cu etichete mai mari, iar în cazul vectorului de tip MaxHeap, orice nod subordonează noduri cu etichete mai mici.

Prezentarea algoritmului:

Fiind dat un vector x cu n componente se cere ca acesta să fie sortat crescător(descrescător) prin metoda Heap-urilor. Vom analiza cazul sortării descrescătoare.

În cazul în care vectorul se organizează ca un MinHeap, este evident că prima componentă reţine cea mai mică valoare (vezi şi exemplul precedent), deci pentru ca vectorul să fie sortat descrescător se organizează ca MinHeap, apoi se schimbă conţinuturile componentelor 1 şi n, deoarece în acest caz, ultima componentă reţine valoarea cea mai mare.

Din prima componentă şi MinHeap-urile cu vârfurile x[2] şi x[3] se formează un nou MinHeap. Se interschimbă conţinuturile componentelor 1 şi n-1.

. . .

Funcţia combinare formează un MinHeap dintr-un vârf şi două MinHeapuri, iar funcţia heap organizează vectorul ca un MinHeap.

Varianta pseudocod a algoritmului:

subalgoritm combinare(vf, n)

baza, valoare, gata întreg;

baza←2*vf; valoare←x[vf];gata←0;

cât timp baza≤n şi gata=0 execută

dacă baza < n si x[baza] > x[baza+1] atunci baza←baza+1

sfârşit dacă;

dacă valoare>x[baza] atunci

x[vf]←x[baza]

vf←baza

baza←baza*2

altfel

gata←1

sfârşit dacă;

sfârşit cât timp;

x[vf]←valoare;

sfârşit combinare;

subalgoritm heap()

i intreg;

pentru i←n/2,1,-1 execută

combinare(i,n);

sfârşit pentru;

sfârşit heap;

subalgoritm heapsort()

aux,i întreg;

heap()

pentru i←n,2,-1 execută

aux←v[1];

v[1] ←v[i];

v[i] ←aux;

combinare(1,i-1);

sfârşit pentru;

sfârşit heapsort;

Implementare C++:

void combinare(int vf, int n){

int baza=2*vf, valoare=x[vf], gata=0;

while(baza<=n && ! gata) {

if(baza < n && x[baza] > x[baza+1]) baza++;

if(valoare>x[baza]) {x[vf]=x[baza];vf=baza;baza=baza*2;}

else gata=1;

}

x[vf]=valoare;

}

void heap(){

int i;

for(i=n/2;i>=1;i--) combinare(i,n);

}

void heapsort(){

int aux;

heap();

for(i=n;i>=2;i--) {

aux=x[1];x[1]=x[i]; x[i]=aux;

combinare(1,i-1);

}

Implementare Pascal:

procedure combinare(vf,n:integer);

var baza, valoare: integer; gata:boolean;

begin

baza:=2*vf; valoare:=x[vf]; gata:=false ;

while(baza<=n) and (not gata) do

begin

if (baza<n) and (x[baza]>x[baza+1]) then baza:=baza+1;

if valoare>x[baza] then

begin

x[vf]:=x[baza];vf:=baza;baza:=baza*2;

end

else gata:=true;

end;

x[vf]:=valoare;

end;

procedure heap;

var i:integer;

begin

for i:=n div 2 downto 1 do combinare(i,n);

end;

procedure heapsort;

var aux:integer;

begin

heap();

for i:=n downto 2 do

begin

aux:=x[1];x[1]:=x[i]; x[i]:=aux;

combinare(1,i-1);

end;

Întrucât algoritmul heapsort apelează de n−1 ori algoritmul combinare care are ordinul de complexitate O(log₂n), iar cum algoritmul descris de funcţia heap are ordinul O(nlog₂n) rezultă că heapsort are de asemenea ordinul O(nlog₂n) .Pentru şiruri mici însă heapsort este ineficient, dar foarte eficient pentru cele mari.

Mergi la pagina METODE DE SORTARE

Aplicatii

Aplicaţie1: Se dă un şir cu n numere întregi. Să se ordoneze descrescător utilizând sortarea cu ansamble.

Program C++:

#include <iostream.h>

#include <conio.h>

int x[100], i, n;

void combinare(int vf, int n)

{int baza=2*vf, valoare=x[vf], gata=0;

while(baza<=n && ! gata)

{if(bazax[baza+1])baza++;

if(valoare>x[baza]) {x[vf]=x[baza];vf=baza;

baza=baza*2;}

else gata=1;

}

x[vf]=valoare;

}

void heap()

{int i;

for(i=n/2;i>=1;i--) combinare(i,n);

}

void heapsort()

{int aux;

heap();

for(i=n;i>=2;i--)

{aux=x[1];x[1]=x[i]; x[i]=aux;

combinare(1,i-1); }

}

void main (){

cin>>n;

for(i=1;i<=n; i++) cin>>x[i];

heapsort();

for(i=1;i<=n; i++)

cout<<x[i]<<” ”;

getch(); }

Program Pascal:

PROGRAM HeapSort1;

VAR x:ARRAY[1..100] OF INTEGER;

i,n:INTEGER;

PROCEDURE combinare(vf,n:INTEGER);

VAR baza, valoare: INTEGER; gata:BOOLEAN;

BEGIN

baza:=2*vf; valoare:=x[vf]; gata:=FALSE ;

WHILE(baza<=n) AND (not gata) DO

BEGIN

IF (baza<n) AND (x[baza]> x[baza+1]) THEN baza:=baza+1;

IF valoare>x[baza] THEN

BEGIN x[vf]:=x[baza];vf:=baza;

baza:=baza*2;END

ELSE gata:=TRUE;

END;

x[vf]:=valoare;

END;

PROCEDURE heap;

VAR i:INTEGER;

BEGIN

FOR i:=n DIV 2 DOWNTO 1 DO combinare(i,n);

END;

PROCEDURE heapsort;

VAR aux:INTEGER;

BEGIN

heap;

FOR i:=n DOWNTO 2 DO BEGIN

aux:=x[1];x[1]:=x[i]; x[i]:=aux;

combinare(1,i-1); END;

END;

BEGIN

READLN(n);

FOR i:=1 TO n DO

READLN(x[i]);

heapsort;

FOR i:=1 TO n DO

WRITE(x[i], ’ ’);

END.

Mergi la pagina METODE DE SORTARE