Structuri de Date Arborescente Implementate Dinamic – Arbore Binar Heap 15
1. Obiectivele lecției:
- Să înțeleagă conceptul de heap și proprietățile acestuia.
- Să învețe cum să implementeze un heap binar.
- Să implementeze operații comune pe heap: inserare, eliminare, max-heapify/min-heapify.
2. Ce este un heap binar?
- Definiție:
Un heap binar este un arbore binar complet care respectă una dintre următoarele proprietăți:- Max-Heap: Valoarea oricărui nod este mai mare sau egală decât valorile copiilor săi.
- Min-Heap: Valoarea oricărui nod este mai mică sau egală decât valorile copiilor săi.
- Proprietăți:
- Este un arbore complet (toate nivelurile, cu excepția ultimului, sunt complet populate).
- Este utilizat frecvent pentru implementarea cozilor de priorități.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Eficient pentru accesarea elementelor de maxim/minim. | Inserarea și eliminarea implică reorganizarea arborelui. |
| Structura este compactă datorită proprietății de arbore complet. | Performanța scade dacă arborele devine dezechilibrat. |
| Util pentru aplicații precum algoritmii de sortare și cozi de priorități. |
4. Reprezentarea unui heap
Heap-urile sunt reprezentate în mod obișnuit folosind:
- Vectori: Copilul stâng și copilul drept ale unui nod se află la pozițiile 2i+12i + 12i+1 și 2i+22i + 22i+2, respectiv.
- Structuri dinamice: Fiecare nod are pointeri către copiii săi.
5. Structura unui nod pentru un heap
struct Nod {
int valoare;
Nod* stanga; // Pointer către copilul stâng
Nod* dreapta; // Pointer către copilul drept
};
6. Implementarea unui Max-Heap
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
2. Inserarea unui element în heap
Inserarea se face astfel:
- Adăugăm elementul într-un loc valid (pentru a păstra proprietatea de arbore complet).
- Reorganizăm arborele pentru a menține proprietatea de heap (numită heapify-up).
void heapifyUp(vector<int>& heap, int index) {
int parinte = (index – 1) / 2;
while (index > 0 && heap[index] > heap[parinte]) {
swap(heap[index], heap[parinte]);
index = parinte;
parinte = (index – 1) / 2;
}
}
void inserare(vector<int>& heap, int valoare) {
heap.push_back(valoare); // Adăugăm elementul la final
heapifyUp(heap, heap.size() – 1); // Reorganizăm arborele
}
3. Eliminarea elementului maxim
Eliminarea elementului maxim (rădăcina) implică:
- Înlocuirea rădăcinii cu ultimul element.
- Eliminarea ultimului element.
- Reorganizarea arborelui pentru a menține proprietatea de heap (numită heapify-down).
void heapifyDown(vector<int>& heap, int index) {
int stanga = 2 * index + 1;
int dreapta = 2 * index + 2;
int celMaiMare = index;
if (stanga < heap.size() && heap[stanga] > heap[celMaiMare]) {
celMaiMare = stanga;
}
if (dreapta < heap.size() && heap[dreapta] > heap[celMaiMare]) {
celMaiMare = dreapta;
}
if (celMaiMare != index) {
swap(heap[index], heap[celMaiMare]);
heapifyDown(heap, celMaiMare);
}
}
void eliminareMax(vector<int>& heap) {
if (heap.empty()) {
cout << „Heap-ul este gol.” << endl;
return;
}
heap[0] = heap.back(); // Înlocuim rădăcina cu ultimul element
heap.pop_back(); // Eliminăm ultimul element
heapifyDown(heap, 0); // Reorganizăm arborele
}
4. Afișarea elementelor din heap
void afisareHeap(const vector<int>& heap) {
for (int valoare : heap) {
cout << valoare << ” „;
}
cout << endl;
}
7. Exemplu complet pentru Max-Heap
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void heapifyUp(vector<int>& heap, int index) {
int parinte = (index – 1) / 2;
while (index > 0 && heap[index] > heap[parinte]) {
swap(heap[index], heap[parinte]);
index = parinte;
parinte = (index – 1) / 2;
}
}
void inserare(vector<int>& heap, int valoare) {
heap.push_back(valoare); // Adăugăm elementul la final
heapifyUp(heap, heap.size() – 1); // Reorganizăm arborele
}
void heapifyDown(vector<int>& heap, int index) {
int stanga = 2 * index + 1;
int dreapta = 2 * index + 2;
int celMaiMare = index;
if (stanga < heap.size() && heap[stanga] > heap[celMaiMare]) {
celMaiMare = stanga;
}
if (dreapta < heap.size() && heap[dreapta] > heap[celMaiMare]) {
celMaiMare = dreapta;
}
if (celMaiMare != index) {
swap(heap[index], heap[celMaiMare]);
heapifyDown(heap, celMaiMare);
}
}
void eliminareMax(vector<int>& heap) {
if (heap.empty()) {
cout << „Heap-ul este gol.” << endl;
return;
}
heap[0] = heap.back(); // Înlocuim rădăcina cu ultimul element
heap.pop_back(); // Eliminăm ultimul element
heapifyDown(heap, 0); // Reorganizăm arborele
}
void afisareHeap(const vector<int>& heap) {
for (int valoare : heap) {
cout << valoare << ” „;
}
cout << endl;
}
int main() {
vector<int> heap;
inserare(heap, 10);
inserare(heap, 20);
inserare(heap, 15);
inserare(heap, 30);
inserare(heap, 40);
cout << „Heap după inserări: „;
afisareHeap(heap);
eliminareMax(heap);
cout << „Heap după eliminarea maximului: „;
afisareHeap(heap);
return 0;
}
8. Activități practice pentru elevi
- Implementați un Min-Heap folosind aceleași metode, modificând condițiile din funcțiile heapifyUp și heapifyDown.
- Scrieți o funcție care sortează un vector utilizând algoritmul Heap Sort.
- Realizați o aplicație care implementează o coadă de priorități utilizând un heap.
9. Scheme logice
- Inserare:
- Adăugăm elementul la sfârșitul arborelui -> Reorganizăm pentru a menține proprietatea de heap.
- Eliminare:
- Înlocuim rădăcina cu ultimul element -> Eliminăm ultimul element -> Reorganizăm arborele.
10. Concluzie
- Heap-urile binare sunt structuri esențiale pentru optimizarea accesului la valorile maxime sau minime.
- Implementarea dinamică permite gestionarea eficientă a resurselor.
- Practica este cheia pentru a înțelege și aplica aceste structuri în probleme complexe.