0% au considerat acest document util (0 voturi)
6 vizualizări2 paginiVector Heap
Documentul descrie structura de date heap, care este un arbore binar în care fiecare nod este mai mic decât fiii săi. Heap-ul este implementat sub forma unui vector, cu cel mai mare element la prima poziție. Algoritmii fundamentali pentru heap sunt Push Heap și Pop Heap.
Încărcat de
Florin BrasoveanuDrepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd
0% au considerat acest document util (0 voturi)
6 vizualizări2 paginiVector Heap
Documentul descrie structura de date heap, care este un arbore binar în care fiecare nod este mai mic decât fiii săi. Heap-ul este implementat sub forma unui vector, cu cel mai mare element la prima poziție. Algoritmii fundamentali pentru heap sunt Push Heap și Pop Heap.
Încărcat de
Florin BrasoveanuDrepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca DOCX, PDF, TXT sau citiți online pe Scribd
Vectorul HEAP
Ce este un Vector Heap (gramadă)
Un heap este o structură de date care are forma unui arbore și care
respectă proprietatea heap, și anume: fiecare nod trebuie să fie mai jos decât
fiecare dintre copiii săi.
Presupun că numele „grămadă” vine de la faptul că, dacă strângi o
grămadă de lucruri, ai prefera să pui lucrurile mari în jos și cele mici în sus dacă
vrei să țină: acesta nu are nicio legătură cu heap, ca regiunea de memorie care
conține obiecte alocate dinamic (spre deosebire de stiva, care se întâmplă să fie
și numele unei structuri de date).
Una dintre cele mai importante proprietăți ale mormanului este că
elementul său cel mai de jos la rădăcină, să fie ușor accesibil.
Într-o grămadă, fiecare nod poate avea, teoretic, orice număr de copii. Dar
în STL, nodurile heap-urilor au doi copii, așa că prin heap se desemneaza heap-
uri binare .
Proprietatea heap, că fiecare nod trebuie să fie mai mic decât copiii săi,
poate fi generalizată la o altă comparație decât „mai mic decât” ca în operatorul
<. Am putea folosi o anumită relație care are mai mult sens pentru tipul de date
care se află în heap. De exemplu, o grămadă de seturi ar putea folosi o relație
lexicografică.
În special, putem folosi și relația „mai mare decât” în proprietatea heap
(care poate fi încă implementată utilizând operator< prin întoarcerea proprietății
heap și asigurându-ne că copiii sunt mai mici decât părinții lor).
Un astfel de heap se numește max heap și acesta este genul de heap pe
care îl are STL. Deci prin heap voi însemna binar max heap în acest articol.
Într-un heap maxim, cel mai mare element este la rădăcină, astfel se poate
observa că fiecare nod este mai jos decât părintele său, iar cel mai mare nod
este la rădăcină.
Folosirea „mai mare decât” ne îndepărtează de metafora grămezilor de
pietre/gunoi/cutii pe care le putem vedea în lumea care ne înconjoară.
Implementarea unui heap
Pentru a reprezenta un arbore binar, cum ar fi un heap, o implementare
este de a face o alocare dinamică pentru fiecare nod, cu 2 pointeri îndreptați
către copiii săi.
Dar există o implementare mult mai eficientă (și elegantă): reprezentarea
acesteia sub forma unui tablou, făcând o traversare în ordinea nivelului a heap-
ului. Spus altfel, înseamnă că matricea începe cu elementul de la rădăcină, apoi
urmează cu copiii acelei rădăcini, apoi cu toți copiii acelor copii. Și apoi
strănepoții. Si asa mai departe.
În acest fel, cel mai mare element se află în prima poziție a matricei.
Aplicații Heap Data Structure:
Heap-ul este utilizat în timpul implementării unei cozi prioritare.
Algoritmul lui Dijkstra
Sortare în grămada
Algoritmi heap
Cei doi algoritmi de heap fundamentali se numesc Push Heap și Pop Heap.
Acești doi algoritmi se pot descrie la patru niveluri, trecând de la algoritm
abstract la implementare concretă:
O descriere generală folosind modelul arborelui
O descriere detaliată folosind modelul arborelui
O descriere detaliată folosind reprezentarea vectorială
O implementare completă ca algoritm generic