Heap-uri folosind Arbori Binari

Ce este Heap`ul (binar) ?

Structura de date Heap este un vector care poate fi vizualizat sub forma unui arbore binar aproape complet.Fiecare nod al arborelui corespunde unui element al vectorului care contine valorile atasate nodurilor.Arborele este plin exceptand ultimul nivel( nivelul inferior), ce se umple de la stanga spre dreapta pana intr-o anumita pozitie.

Radacina arborelui este pe primul nivel A[1] spre exemplu. Pentru orice indice i dat ce corespunde unui nod se poate calcula usor indicele parintelui acestuia ( [i/2], i > 1) respectiv fii acestuia ( i * 2 = fiul stanga, i * 2 <= lungime[A], i *2+1 = fiul dreapta,i*2+1 <= lungime[A]) unde lungime[A] reprezinta numarul elementelor ce sunt in vector.

Exemplu de Arbore Binar si un vector ce il reprezinta pe acesta ca Heap:

Vector ce reprezinta un Heap : 100 19 36 17 3 25 1 2 7

Un max-heap este un arbore binar complet in care valoarea memorata in orice nod al sau este mai mare sau egala decat valorile memorate in nodurile fii ai acestuia.
Corespunzator se poate defini min-heap-ul, ca un arbore binar complet in care valoarea memorata in orice nod este mai mica sau egala decat valorile memorate in nodurile fii ai acestuia.

Deoarece elementele unui heap apartin unui arbore binar putem spune ca inaltimea heap`ului este log₂(n).

O structura de acest tip permite efectuarea operatiilor de baza intr-un timp foarte bun :

• Cautarea minimului in O(1)
• Crearea unei structuri de heap dintr-un vector oarecare in O(N)
• Eliminarea unui element in O(log N)
• Inserarea unui element in O(log N)
• Sortarea elementelor din heap in O(N log N)

In acest articol ne vom „juca” cu un Max Heap deci radacina arborelui va reprezenta maximul acestui vector.

Vom defini cateva lucruri initial pentru a ne usura lucrul si pentru a intelege mai usor la ce ne referim cand facem un lucru :

#define MAX_N 1000
int Heap[MAX_N];
inline int Parinte(int i) { return i/2; }
inline int FiuStang(int i) { return i * 2; }
inline int FiuDrept(int i) { return i*2+1; }

Cum cautam maximul ?

Evident ca trebuie doar sa returnam valoarea din radacina arborelui.

inline int max()
{
   return Heap[1];
}

Cum cream o structura heap?

Pentru a face asta exista 2 situatii pe care le vom analiza :

• Situatia in care nodul trebuie coborat in arbore, folosind o tehnica ce se numeste sift
• Situatia in care nodul trebuie urcat in arbore, folosind o tehnica ce se numeste percolate

1. Tehnica sift
Sa consideram ca avem un vector ce reprezinta un heap cu exceptia uneia dintre valori (sa ne imaginam valoarea 5),ce se afla in interiorul arborelui.Aceata valoare este mai mica decat fii ei (9 si 10).Evident ca valoarea 5 trebuie sa coboare in arbore.Dar care dintr e valori urca in locul ei?Daca alegem valoarea 9 eroarea inca persista,dar daca alegem valoarea 10 totul devine ok.Inseamna ca in locul valorii 5 trebuie sa aducem maximul dintre fii ei(daca exista).Avand in vedere ca au avut loc modificari trebuie sa ne asiguram ca valorile interschimbate nu au creat erori mai jos in arbore.Tehnica se repeta pana se atinge nivelul frunzelor . 🙂

void heapDown(int v) //sift
{
	int w = v*2;
	while(w < n)
	{
		if(w+1 < n && Heap[w+1] > Heap[w]) w++; //alegem maximul dintre cei 2 fii
		if(Heap[v] >= Heap[w]) return;   //maximul dintre cei 2 fii nu trebuie sa modifice parintele lor ?
		//interschimbam parintele cu fiul maxim
               Heap[v] ^= Heap[w] ^= Heap[v] ^= Heap[w]; 
		v = w;
		w *= 2;
	}
}

2. Tehnica percolate
Sa consideram urmatorul exemplu : Avem un vector ,respectiv un arbore binar ce reprezinta un heap construit corect si urmeaza sa adaugam o noua valoare ce este mai mare decat anumite valori.Cum aflam pozitia unde trebuie pusa aceasta noua valoare pentru ca intreg arborele sa reprezinte un heap?Valoarea noua introdusa trebuie sa „urce” in arbore.Pentru aceasta trebuie comparata valoarea cu parintele ei si interschimbat cu acesta atat timp cat noua valoare este mai mare ca parintele ei.

void heapUp(int v) //percolate
{
	int k = Heap[v];
	while(v && k > Heap[v/2])
	{
		Heap[v] ^= Heap[v/2] ^=  Heap[v] ^= Heap[v/2];
		v/=2;
	}
	Heap[v] = k;
}

Cum construim un heap,avand un vector cu valori ce nu respecta conditiile de Max Heap?

Pentru a construi un heap si respectiv un arbore binar ce respecta conditiile unui Max Heap procedura heapUp() trebuie folosita de jos in sus pentru un arborele binar existent.Datorita faptului ca elementele din vector cuprinse intre [[n/2]+1,n] sunt frunze acestea pot fi considerate heap`uri formate din cate un singur element.Astfel procedura pentru construirea heap`ului poate incepe cu n/2.

void buildHeap()
{
	for(int i = n/2; i>=0; i--) //n = numarul de elemente
	{
		heapDown(i); //sift
	}
}

Cum adaugam o noua valoare intr-un Heap?

Daca ai inteles acest articol pana acum cred ca banuiesti. 😀 Adaugam o noua valoare in vector si incercam sa o „ridicam” atat cat ne permit „parintii”.

void addHeap(int k)
{
	Heap[++n] = k;
	heapUp(n);
}

Cum stergem o valoare dintr-un Heap?

Daca ai citit explicatiile cu atentie de la tehnica sift banuiesti ca ea urmeaza sa fie folosita(dar nu numai ea 🙂 ) .Sa presupunem ca dorim sa stergem o valoare din arbore.Cu ce valoare umplem acea pozitie?
Simplu :D. Singura valoare din arbore ce poate sa umple vectorul fara a distruge arborele este ultima valoare din vector.Astfel vectorul isi micsoreaza dimensiunea cu 1,ultima valoare ii preia locul valorii eliminate.
Cum refacem heap`ul?
Hmm,aici exista 2 situatii : situatia in care valoarea adusa in locul celei sterse este mai mare ca parintele ei,aici trebuie sa urcam valoarea in arbore(implicit folosim tehnica percolate) si situatia cand este mai mica sau egala cu aceasta.In aceasta situatie nu trebuie sa verificam nimic mai sus de parintele pozitiei sterse dar exista posibilitatea ca fii valorii modificate sa fie mai mici.Inseamna ca trebuie sa ne asiguram unde ii este locul valorii noi,in jos(folosind,ati ghicit, tehnica sift).

void delHeap(int v)
{
	Heap[v] = Heap[--n];
	if(v && Heap[v] > Heap[v/2])
		heapDown(v); //sift
	else
		heapUp(a,v); //percolate
}

Cum cautam o valoare intr-un Heap?

Desi, Heap`urile binare nu sunt folosite pentru a cauta un vector,datorita faptului ca timpul de executie este O(n), se poate teoretic reduce acest timp.Sa presupunem ca nu gasim valoare la pozitia i,avem 2 situatii : cautam in fiul stang sau fiul drept.Practic daca gasim in fiul stang nu trebuie sa mai cautam si in cel drept.Astfel exista posibilitatea in aplicatii ca aceasta valoare sa fie mai redusa de O(n),insa in cazul in care valoarea nu exista timpul este constant si liniar.

int search(int k,int v)
{
	int ans = -1,r;
	if(Heap[v] == k) ans = v;
    else
    {
	    if(v*2+1 < n)
        {					
			r = search(k,v*2+1);
		    ans = ans == -1 ? r : ans;
		}
		
		if(v*2+2 < n && ans == -1) 
		{			
			r = search(k,v*2+2);
		    ans = ans == -1 ? r : ans;
		}		 
	}
	return ans;
}

Daca ati citit pana aici va sugerez sa aruncati o privire si mai jos pe temele propuse 😀
1. Problema Heap`uri
2. Gasiti un algoritm de timp O(n*lg k) pentru a interclasa k liste ordonate,unde n este numarul total de elemente din listele de intrare.