Structuri de Date Arborescente Implementate Dinamic – Arbore Parțial de Cost Minim
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore parțial de cost minim (Minimum Spanning Tree – MST).
- Să învețe algoritmii clasici pentru determinarea MST: Kruskal și Prim.
- Să implementeze MST folosind structuri dinamice.
2. Ce este un arbore parțial de cost minim?
- Definiție:
Un arbore parțial de cost minim este un subgraf al unui graf ponderat, conex și neorientat, care:- Include toate nodurile grafului.
- Are cel mai mic cost total posibil (suma ponderilor muchiilor).
- Este un arbore (nu conține cicluri).
- Proprietăți:
- Un graf poate avea mai mulți MST cu același cost.
- Numărul muchiilor dintr-un MST este întotdeauna V−1V – 1V−1, unde VVV este numărul de noduri.
3. Aplicații practice ale MST
- Construcția rețelelor (electricitate, drumuri, internet).
- Compresia datelor (algoritmul lui Huffman).
- Optimizarea resurselor într-o organizație.
4. Algoritmi clasici pentru MST
- Algoritmul lui Kruskal:
- Ideea principală: Selectează muchiile grafului în ordine crescătoare a costurilor, asigurându-se că nu se formează cicluri.
- Pași:
- Sortează muchiile grafului după cost.
- Adaugă fiecare muchie (în ordine) dacă nu formează un ciclu.
- Algoritmul lui Prim:
- Ideea principală: Construiește MST pornind de la un nod inițial și adăugând muchii de cost minim care conectează noduri noi.
- Pași:
- Alege un nod de pornire.
- Selectează muchia de cost minim care leagă un nod inclus cu un nod neinclus.
5. Implementarea algoritmului lui Kruskal
Structura pentru reprezentarea grafului
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Muchie {
int sursa, destinatie, cost;
};
// Comparator pentru sortarea muchiilor după cost
bool comparaMuchii(const Muchie& a, const Muchie& b) {
return a.cost < b.cost;
}
Reprezentarea Uniunii și Găsirii (Union-Find)
struct DisjointSet {
vector<int> parinte, rang;
DisjointSet(int n) {
parinte.resize(n);
rang.resize(n, 0);
for (int i = 0; i < n; i++) {
parinte[i] = i;
}
}
int gaseste(int u) {
if (u != parinte[u]) {
parinte[u] = gaseste(parinte[u]);
}
return parinte[u];
}
void uneste(int u, int v) {
u = gaseste(u);
v = gaseste(v);
if (u != v) {
if (rang[u] < rang[v]) {
parinte[u] = v;
} else if (rang[u] > rang[v]) {
parinte[v] = u;
} else {
parinte[v] = u;
rang[u]++;
}
}
}
};
Algoritmul lui Kruskal
int kruskalMST(vector<Muchie>& muchii, int numarNoduri) {
sort(muchii.begin(), muchii.end(), comparaMuchii); // Sortează muchiile după cost
DisjointSet ds(numarNoduri);
int costTotal = 0;
vector<Muchie> rezultat;
for (const auto& muchie : muchii) {
if (ds.gaseste(muchie.sursa) != ds.gaseste(muchie.destinatie)) {
rezultat.push_back(muchie);
costTotal += muchie.cost;
ds.uneste(muchie.sursa, muchie.destinatie);
}
}
cout << „Muchiile din MST:\n”;
for (const auto& muchie : rezultat) {
cout << muchie.sursa << ” – ” << muchie.destinatie << ” : ” << muchie.cost << endl;
}
return costTotal;
}
Exemplu de utilizare
int main() {
int numarNoduri = 4;
vector<Muchie> muchii = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
int costTotal = kruskalMST(muchii, numarNoduri);
cout << „Costul total al MST: ” << costTotal << endl;
return 0;
}
6. Implementarea algoritmului lui Prim
Structura pentru reprezentarea grafului
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> Pereche; // cost, nod
Algoritmul lui Prim
int primMST(vector<vector<Pereche>>& graf, int numarNoduri) {
priority_queue<Pereche, vector<Pereche>, greater<Pereche>> pq;
vector<bool> inclus(numarNoduri, false);
int costTotal = 0;
pq.push({0, 0}); // Pornim de la nodul 0 cu cost 0
while (!pq.empty()) {
int cost = pq.top().first;
int nod = pq.top().second;
pq.pop();
if (inclus[nod]) continue;
inclus[nod] = true;
costTotal += cost;
for (const auto& vecin : graf[nod]) {
if (!inclus[vecin.second]) {
pq.push(vecin);
}
}
}
return costTotal;
}
Exemplu de utilizare
int main() {
int numarNoduri = 5;
vector<vector<Pereche>> graf(numarNoduri);
graf[0].push_back({2, 1});
graf[0].push_back({3, 3});
graf[1].push_back({2, 0});
graf[1].push_back({5, 2});
graf[1].push_back({8, 3});
graf[2].push_back({5, 1});
graf[2].push_back({7, 3});
graf[3].push_back({3, 0});
graf[3].push_back({8, 1});
graf[3].push_back({7, 2});
int costTotal = primMST(graf, numarNoduri);
cout << „Costul total al MST: ” << costTotal << endl;
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care verifică dacă un graf are mai mulți arbori parțiali de cost minim.
- Adăugați opțiuni de a construi un graf utilizând matricea de adiacență și lista de adiacență.
- Implementați o aplicație care compară costurile MST folosind algoritmii lui Kruskal și Prim.
8. Scheme logice
- Algoritmul lui Kruskal:
- Sortează muchiile -> Verifică ciclurile -> Adaugă muchiile valide în MST.
- Algoritmul lui Prim:
- Selectează un nod inițial -> Găsește muchia de cost minim -> Adaugă nodul conectat.
9. Concluzie
- Arborii parțiali de cost minim sunt esențiali pentru optimizarea resurselor în grafuri.
- Algoritmii lui Kruskal și Prim sunt eficienți pentru rezolvarea MST.
- Practica ajută la înțelegerea algoritmilor și la aplicarea lor în situații reale.
Structuri de Date Arborescente Implementate Dinamic – Arbori Binari
1. Obiectivele lecției:
- Să înțeleagă conceptul de arbore binar și proprietățile acestuia.
- Să învețe cum să implementeze un arbore binar dinamic.
- Să implementeze operații comune pe arbori binari: inserare, căutare, traversare (în ordine, preordine, postordine).
2. Ce este un arbore binar?
- Definiție:
Un arbore binar este o structură de date arborescentă în care fiecare nod are cel mult doi copii:- Subarborele stâng
- Subarborele drept
- Proprietăți:
- Arborele binar poate fi complet, perfect sau degenerat.
- Într-un arbore binar, numărul maxim de noduri la nivelul hhh este 2h2^h2h.
- Înălțimea arborelui este dată de lungimea drumului de la rădăcină la cea mai adâncă frunză.
- Tipuri de arbori binari:
- Arbore binar complet: Fiecare nivel, cu excepția ultimului, este complet populat.
- Arbore binar de căutare (BST): Subarborele stâng conține valori mai mici, iar subarborele drept conține valori mai mari decât rădăcina.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Structură flexibilă pentru gestionarea datelor ierarhice. | Gestionarea dinamică necesită atenție pentru integritate. |
| Traversare eficientă pentru căutare, inserare și ștergere. | Performanța poate scădea în cazuri de arbori dezechilibrați. |
| Este baza pentru alte structuri complexe, cum ar fi heap-uri. |
4. Structura unui nod
struct Nod {
int valoare; // Valoarea stocată în nod
Nod* stanga; // Pointer către subarborele stâng
Nod* dreapta; // Pointer către subarborele drept
};
5. Operații comune pe arbori binari
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 nod într-un arbore binar de căutare (BST)
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
3. Traversări ale arborelui
- Traversare în ordine (in-order):
Vizitează nodurile în ordinea: stânga → rădăcină → dreapta.
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
- Traversare preordine (pre-order):
Vizitează nodurile în ordinea: rădăcină → stânga → dreapta.
void traversarePreOrdine(Nod* radacina) {
if (radacina == nullptr) return;
cout << radacina->valoare << ” „;
traversarePreOrdine(radacina->stanga);
traversarePreOrdine(radacina->dreapta);
}
- Traversare postordine (post-order):
Vizitează nodurile în ordinea: stânga → dreapta → rădăcină.
void traversarePostOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversarePostOrdine(radacina->stanga);
traversarePostOrdine(radacina->dreapta);
cout << radacina->valoare << ” „;
}
4. Căutarea unui element
bool cautaValoare(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return false;
}
if (valoare == radacina->valoare) {
return true;
} else if (valoare < radacina->valoare) {
return cautaValoare(radacina->stanga, valoare);
} else {
return cautaValoare(radacina->dreapta, valoare);
}
}
5. Ștergerea unui nod
Nod* stergeNod(Nod* radacina, int valoare) {
if (radacina == nullptr) return radacina;
if (valoare < radacina->valoare) {
radacina->stanga = stergeNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = stergeNod(radacina->dreapta, valoare);
} else {
if (radacina->stanga == nullptr) {
Nod* temp = radacina->dreapta;
delete radacina;
return temp;
} else if (radacina->dreapta == nullptr) {
Nod* temp = radacina->stanga;
delete radacina;
return temp;
}
Nod* temp = radacina->dreapta;
while (temp->stanga != nullptr) {
temp = temp->stanga;
}
radacina->valoare = temp->valoare;
radacina->dreapta = stergeNod(radacina->dreapta, temp->valoare);
}
return radacina;
}
6. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* stanga;
Nod* dreapta;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->stanga = nullptr;
nod->dreapta = nullptr;
return nod;
}
Nod* insereazaNod(Nod* radacina, int valoare) {
if (radacina == nullptr) {
return creeazaNod(valoare);
}
if (valoare < radacina->valoare) {
radacina->stanga = insereazaNod(radacina->stanga, valoare);
} else if (valoare > radacina->valoare) {
radacina->dreapta = insereazaNod(radacina->dreapta, valoare);
}
return radacina;
}
void traversareInOrdine(Nod* radacina) {
if (radacina == nullptr) return;
traversareInOrdine(radacina->stanga);
cout << radacina->valoare << ” „;
traversareInOrdine(radacina->dreapta);
}
int main() {
Nod* radacina = nullptr;
radacina = insereazaNod(radacina, 50);
insereazaNod(radacina, 30);
insereazaNod(radacina, 70);
insereazaNod(radacina, 20);
insereazaNod(radacina, 40);
insereazaNod(radacina, 60);
insereazaNod(radacina, 80);
cout << „Traversare în ordine: „;
traversareInOrdine(radacina);
cout << endl;
return 0;
}
6. Activități practice pentru elevi
- Implementați o funcție care calculează înălțimea unui arbore binar.
- Scrieți un program care determină dacă un arbore este echilibrat.
- Implementați o funcție pentru numărarea nodurilor frunză dintr-un arbore binar.
7. Scheme logice
- Inserare:
- Verifică dacă nodul curent este gol -> Creează un nou nod -> Compară valoarea și inserează în stânga sau dreapta.
- Traversare:
- Utilizează recursivitate pentru a parcurge nodurile în ordinea specificată.
- Căutare:
- Compară valoarea căutată cu nodul curent -> Explorează subarborele corespunzător.
8. Concluzie
- Arborii binari sunt structuri de date versatile utilizate în multe aplicații informatice.
- Implementarea dinamică permite gestionarea eficientă a memoriei și flexibilitatea dimensiunii arborelui.
Structuri de Date Arborescente Implementate Dinamic – Arbore Binar Heap
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.
Ștergerea nodului rădăcină în Min-Heap/Max-Heap
1. Concept general:
Ștergerea nodului rădăcină dintr-un heap presupune eliminarea elementului care respectă proprietățile heap-ului:
- Max-Heap: Nodul rădăcină este cel mai mare element.
- Min-Heap: Nodul rădăcină este cel mai mic element.
Pașii generali pentru ștergerea rădăcinii:
- Înlocuim rădăcina cu ultimul element din heap.
- Eliminăm ultimul element din vector sau structură.
- Aplicăm procesul de reorganizare a heap-ului, numit heapify-down, pentru a restabili proprietatea de heap.
2. Implementarea pentru Max-Heap
Heapify-Down în Max-Heap
Această funcție rearanjează elementele astfel încât proprietatea Max-Heap să fie restabilită după ștergerea rădăcinii.
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);
}
}
Ștergerea rădăcinii din Max-Heap
- Înlocuim rădăcina cu ultimul element din vector.
- Eliminăm ultimul element.
- Reorganizăm arborele folosind heapifyDown.
void stergeRadacinaMaxHeap(vector<int>& heap) {
if (heap.empty()) {
cout << „Heap-ul este gol. Nu există elemente de șters.” << 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
}
3. Implementarea pentru Min-Heap
Heapify-Down în Min-Heap
Funcția rearanjează elementele astfel încât proprietatea Min-Heap să fie restabilită după ștergerea rădăcinii.
void heapifyDownMin(vector<int>& heap, int index) {
int stanga = 2 * index + 1;
int dreapta = 2 * index + 2;
int celMaiMic = index;
if (stanga < heap.size() && heap[stanga] < heap[celMaiMic]) {
celMaiMic = stanga;
}
if (dreapta < heap.size() && heap[dreapta] < heap[celMaiMic]) {
celMaiMic = dreapta;
}
if (celMaiMic != index) {
swap(heap[index], heap[celMaiMic]);
heapifyDownMin(heap, celMaiMic);
}
}
Ștergerea rădăcinii din Min-Heap
- Înlocuim rădăcina cu ultimul element din vector.
- Eliminăm ultimul element.
- Reorganizăm arborele folosind heapifyDownMin.
void stergeRadacinaMinHeap(vector<int>& heap) {
if (heap.empty()) {
cout << „Heap-ul este gol. Nu există elemente de șters.” << endl;
return;
}
heap[0] = heap.back(); // Înlocuim rădăcina cu ultimul element
heap.pop_back(); // Eliminăm ultimul element
heapifyDownMin(heap, 0); // Reorganizăm arborele
}
4. Exemplu complet
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Heapify-Down pentru Max-Heap
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);
}
}
// Ștergerea rădăcinii pentru Max-Heap
void stergeRadacinaMaxHeap(vector<int>& heap) {
if (heap.empty()) {
cout << „Heap-ul este gol. Nu există elemente de șters.” << endl;
return;
}
heap[0] = heap.back();
heap.pop_back();
heapifyDown(heap, 0);
}
// Funcție pentru afișarea Heap-ului
void afisareHeap(const vector<int>& heap) {
for (int val : heap) {
cout << val << ” „;
}
cout << endl;
}
int main() {
vector<int> maxHeap = {40, 30, 20, 10, 15, 5, 25};
cout << „Heap inițial: „;
afisareHeap(maxHeap);
stergeRadacinaMaxHeap(maxHeap);
cout << „Heap după ștergerea rădăcinii: „;
afisareHeap(maxHeap);
return 0;
}
5. Activități practice pentru elevi
- Implementați ștergerea rădăcinii pentru un Min-Heap.
- Extindeți funcțiile pentru a implementa Heap Sort utilizând un Max-Heap.
- Realizați un program care implementează o coadă de priorități utilizând Min-Heap.
6. Scheme logice
- Ștergerea rădăcinii:
- Înlocuiți rădăcina cu ultimul element din vector.
- Eliminați ultimul element.
- Reorganizați arborele cu heapify-down pentru a menține proprietatea heap-ului.
7. Concluzie
- Ștergerea rădăcinii este o operație esențială pentru gestionarea heap-urilor și este utilizată frecvent în algoritmi precum Heap Sort sau cozi de priorități.
- Implementarea funcției heapifyDown este crucială pentru a menține proprietățile heap-ului.
- Practica cu Max-Heap și Min-Heap ajută la înțelegerea utilizării eficiente a acestor structuri de date.