InformaticăliceuClasa 11mediu
Heap și Priority Queue în C++
Structura de date Heap: implementare, operații și utilizare prin STL priority_queue.
2 luni în urmă
0 vizualizări
30 minute
Heap și Priority Queue în C++
Ce este un Heap?
Un heap binar este un arbore binar complet unde:
- •Max-Heap: părintele >= copii
- •Min-Heap: părintele <= copii
Implementare Manuală (Max-Heap)
1#include <iostream> 2#include <vector> 3using namespace std; 4 5class MaxHeap { 6private: 7 vector<int> heap; 8 9 int parinte(int i) { return (i - 1) / 2; } 10 int stang(int i) { return 2 * i + 1; } 11 int drept(int i) { return 2 * i + 2; } 12 13 void siftUp(int i) { 14 while (i > 0 && heap[parinte(i)] < heap[i]) { 15 swap(heap[parinte(i)], heap[i]); 16 i = parinte(i); 17 } 18 } 19 20 void siftDown(int i) { 21 int maxIdx = i; 22 int st = stang(i); 23 int dr = drept(i); 24 25 if (st < heap.size() && heap[st] > heap[maxIdx]) 26 maxIdx = st; 27 if (dr < heap.size() && heap[dr] > heap[maxIdx]) 28 maxIdx = dr; 29 30 if (i != maxIdx) { 31 swap(heap[i], heap[maxIdx]); 32 siftDown(maxIdx); 33 } 34 } 35 36public: 37 void insert(int val) { 38 heap.push_back(val); 39 siftUp(heap.size() - 1); 40 } 41 42 int getMax() { 43 return heap[0]; 44 } 45 46 int extractMax() { 47 int maxVal = heap[0]; 48 heap[0] = heap.back(); 49 heap.pop_back(); 50 if (!heap.empty()) 51 siftDown(0); 52 return maxVal; 53 } 54 55 bool empty() { return heap.empty(); } 56 int size() { return heap.size(); } 57};
STL Priority Queue
1#include <queue> 2using namespace std; 3 4int main() { 5 // Max-Heap (implicit) 6 priority_queue<int> maxHeap; 7 maxHeap.push(30); 8 maxHeap.push(10); 9 maxHeap.push(50); 10 maxHeap.push(20); 11 12 while (!maxHeap.empty()) { 13 cout << maxHeap.top() << " "; // 50 30 20 10 14 maxHeap.pop(); 15 } 16 cout << endl; 17 18 // Min-Heap 19 priority_queue<int, vector<int>, greater<int>> minHeap; 20 minHeap.push(30); 21 minHeap.push(10); 22 minHeap.push(50); 23 24 while (!minHeap.empty()) { 25 cout << minHeap.top() << " "; // 10 30 50 26 minHeap.pop(); 27 } 28 29 return 0; 30}
Heap cu Structuri Custom
1struct Task { 2 int prioritate; 3 string nume; 4 5 // Pentru Max-Heap: cel cu prioritate mai mare e "mai mic" 6 bool operator<(const Task& other) const { 7 return prioritate < other.prioritate; 8 } 9}; 10 11priority_queue<Task> taskQueue; 12taskQueue.push({3, "Email"}); 13taskQueue.push({1, "Backup"}); 14taskQueue.push({5, "Urgent"}); 15 16cout << taskQueue.top().nume << endl; // Urgent
Complexitate
| Operație | Complexitate |
|---|---|
| Insert | O(log n) |
| Get Max/Min | O(1) |
| Extract Max/Min | O(log n) |
| Build Heap | O(n) |
Aplicații
- •Heap Sort
- •Dijkstra, Prim
- •Median dinamic
- •Top K elemente
Tutorialul te-a ajutat?
Dacă ai nevoie de ajutor personalizat, găsește un profesor calificat pentru meditații
