Ștergerea nodului rădăcină în Min-Heap/Max-Heap 16
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.