O structură de date Heap este un arbore binar complet, cu proprietatea că o cheie-părinte este mai mică (in cazul min Heap)/mai mare (în cazul max Heap) decât toți fiii săi. În realitate, arborele se reprezintă ca un vector în care „nodul” aflat pe poziția i are ca părinte un nod de pe poziție (i-1)/2 , iar fiii săi se află pe pozițiile 2*i+1 respectiv 2*i+2 din vector.
În următorul program din C, se creează un Heap dintr-un vector, inițial cu elemente în ordinea vectorului (nerespectând proprietatea); după care se mută elementele in așa fel încât să se respecte proprietatea de Heap.
Dintr-un Heap se pot extrage cu ușurință elementele minime pentru ca reprezintă poziția 0 din vector (sau rădăcina din arborele imaginat), și astfel tot extrăgând minimul se obține o listă sortată cu o complexitate N*log N.
După ce se extrage un element din Heap, se alege ultimul element din vectorul de Heap (a cărei poziție este sigur ocupată) și se mută de la rădăcină, în căutarea unui loc potrivit in Heap unde să fie respectată proprietatea. Astfel, Heap-ul este refăcut.
Când se adaugă un element, se adaugă inițial la sfârșit după care se urcă în căutarea unui loc potrivit, cum am spus și mai sus.
#include "stdio.h"
#include"stdlib.h"
typedef struct heap_vector_struct
{
// Vectorul de elemente
int *values;
// Dimensiunea heap-ului
int dimVect;
// Capacitatea (dimensiunea maxima)
int capVect;
} HeapVector;
HeapVector* CreeazaVector(int *value, int dimV, int capV) {
HeapVector * HV;
HV=(HeapVector*)malloc(sizeof(HeapVector));
HV->dimVect=dimV;
HV->capVect=capV;
HV->values=(int*)malloc(capV*sizeof(int));
int i;
printf("vectorul meu:\n");
for (i=0;i<=dimV-1; i++){
HV->values[i]=value[i];
printf("%d ",value[i]);}
printf("\n");
return HV;
}
void ElibereazaVector(HeapVector *h) {
free(h->values);
free(h);
}
// returneaza pozitia parintelui
int Parinte(HeapVector *h, int poz) {
if (h->values[(poz-1)/2])
return (poz-1)/2;
return -1;
}
int DescS(HeapVector *h, int poz) { //pozitie fiu stanga
if (h->values[2*poz+1])
return 2*poz+1;
return -1;
}
int DescD(HeapVector *h, int poz) { //pozitie fiu dreapta, daca exista
if (h->values[2*poz+2])
return 2*poz+2;
return -1;
}
int min(int a , int b, int c) {
int y=a;
if (y > b)
y=b;
if (y > c)
y=c;
return y;
}
void InterschimbaValori(HeapVector *h, int a , int b) {
int c=h->values[a];
h->values[a]=h->values[b];
h->values[b]=c;
}
void CoboaraValoare(HeapVector *h, int poz) {
int pozDesc=0;
while(1) {
if (DescD(h,poz) && DescS(h,poz)) {
int valMin = min(h->values[poz], h->values[DescS(h,poz)],h->values [DescD(h,poz)]);
if (valMin == h->values[poz])
return; // nimic de facut
if (valMin == h->values[DescS(h,poz)])
pozDesc =DescS(h,poz);
else
pozDesc = DescD(h,poz);
InterschimbaValori(h,poz, pozDesc);
poz = pozDesc;
}
else return;
}
}
void CoboaraValoaresort(HeapVector *h, int poz) {
int pozDesc=0;
while (1) {
if (DescD(h,poz)&&DescS(h,poz)) {
int valMin = min(h->values[poz], h->values[DescS(h,poz)],h->values [DescD(h,poz)]);
if (valMin == h->values[poz])
return; // nimic de facut
if (valMin == h->values[DescS(h,poz)])
pozDesc =DescS(h,poz);
else
pozDesc = DescD(h,poz);
InterschimbaValori(h,poz, pozDesc);
poz = pozDesc;
}
}
}
void UrcaValoare(HeapVector *h, int poz) {
while (poz > 0 && h->values[poz] > h->values[Parinte(h,poz)]) {
// ... interschimbam nodul curent cu parintele
InterschimbaValori(h,poz, Parinte(h,poz));
// Urcam pozitia curenta mai sus cu un nivel si reluam
poz = Parinte(h,poz);
}
}
int Minim(HeapVector *h) {
return h->values[0];
}
int ExtrageMinim(HeapVector *h) { // ia minimul si il sterge
int min=h->values[0];
int g=h->dimVect-1;
InterschimbaValori(h,0,g);
h->dimVect--;
CoboaraValoare(h,0);
return min;
}
void ConstruiesteHeap(HeapVector *h) {
int i;
for (i=h->dimVect/2; i>= 0; i--)
CoboaraValoare(h,i);
}
void AdaugaValoare(HeapVector *h, int val) {
h->dimVect++;
if (h->capVectdimVect) {
h->capVect++;
h->values=(int*)realloc(h,h->capVect*sizeof(int));
}
h->values[h->dimVect-1]=val;
UrcaValoare(h,h->dimVect-1);
}
void HeapSort1(HeapVector *h) {
int *minim;
minim=(int*)malloc(h->dimVect*sizeof(int));
int i;
for(i=0;idimVect; i++){
minim[i]=ExtrageMinim(h);
printf("%d ", minim[i]); }
}
int main () {
int i,p, *s;
s=(int*)malloc(30*sizeof(int));
for(i=0;i<=13 ;i++)
scanf("%d",&s[i];
HeapVector *H;
H=CreeazaVector(s,14,30);
ConstruiesteHeap(H);
printf("asta e heapul:");
for (i=0; i<=13;i++)
printf("%d ",H->values[i]);
printf("\nvectorul sortat :");
HeapSort1(H);
printf("\nvectorul sortat");
for (i=0;i<=9;i++)
printf("%d ",H->values[i]);
ElibereazaVector(H);
return 0;
}
