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)

Copiază
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

Copiază
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

Copiază
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

Aplicații

• •Heap Sort
• •Dijkstra, Prim
• •Median dinamic
• •Top K elemente