• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Heap-uri folosind Arbori Binari

2
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 9 iul., 2009 at 5:27 pm

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:

Arbore binar ce are Max Heap

Arbore binar ce are Max 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 log2(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.

Etichete: arborearbore binarHeapheap binarMax HeapMin Heappercolatesift

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Gmail out from Beta
  • Articolul următor Google Chrome OS

2 Comentarii

  1. alin spune:
    mai 5, 2010 la 8:39 pm

    ma intereseaza in special despre forma poloneza a arborilor….as avea nevoie de niste informatii legate de aceasta tema..ms

  2. Avadanei Andrei spune:
    mai 5, 2010 la 8:54 pm

    Salut Alin,

    Ai cateva informatii legate de forma poloneza aici. Daca vei dori lamuriri suplimentare nu ezita sa ne anunti.


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • iunie 2022
    L Ma Mi J V S D
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Heap-uri folosind Arbori Binari
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons