Priority Queue (Heap)

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Task {
5
    int priority;   // smaller number = higher priority
6
    int id;         // tie-breaker
7
};
8
9
// Custom comparator for a min-heap of Task by (priority, id)
10
struct TaskCmp {
11
    bool operator()(const Task &a, const Task &b) const {
12
        // priority_queue puts the element considered "largest" at top.
13
        // Returning true means a should come after b.
14
        // To make a min-heap by (priority, id), we return true if a > b lexicographically.
15
        if (a.priority != b.priority) return a.priority > b.priority; // smaller priority is better
16
        return a.id > b.id; // tie-break by smaller id first
17
    }
18
};
19
20
int main() {
21
    // 1) Default max-heap of ints
22
    priority_queue<int> maxpq; // top() is the largest
23
    for (int x : {5, 1, 7, 3}) maxpq.push(x);
24
    cout << "Max-heap order: ";
25
    while (!maxpq.empty()) {
26
        cout << maxpq.top() << ' ';
27
        maxpq.pop();
28
    }
29
    cout << "\n";
30
31
    // 2) Min-heap of ints using greater<int>
32
    priority_queue<int, vector<int>, greater<int>> minpq; // top() is the smallest
33
    for (int x : {5, 1, 7, 3}) minpq.push(x);
34
    cout << "Min-heap order: ";
35
    while (!minpq.empty()) {
36
        cout << minpq.top() << ' ';
37
        minpq.pop();
38
    }
39
    cout << "\n";
40
41
    // 3) Min-heap of custom tasks with tie-breaks
42
    priority_queue<Task, vector<Task>, TaskCmp> tasks;
43
    tasks.push({3, 42});
44
    tasks.push({1, 10});
45
    tasks.push({1, 5});
46
    tasks.push({2, 7});
47
48
    cout << "Tasks by (priority,id): ";
49
    while (!tasks.empty()) {
50
        auto t = tasks.top(); tasks.pop();
51
        cout << '(' << t.priority << ',' << t.id << ") ";
52
    }
53
    cout << "\n";
54
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Dijkstra with non-negative edge weights.
5
// Uses a min-heap of pairs (dist, node). Lazy deletion ignores stale entries.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n, m, s; // nodes [0..n-1], edges, source
12
    cin >> n >> m >> s;
13
    vector<vector<pair<int,int>>> g(n); // (neighbor, weight)
14
    for (int i = 0; i < m; ++i) {
15
        int u, v, w; cin >> u >> v >> w;
16
        g[u].push_back({v, w});
17
        g[v].push_back({u, w}); // comment out if directed
18
    }
19
20
    const long long INF = (1LL<<60);
21
    vector<long long> dist(n, INF);
22
    dist[s] = 0;
23
24
    using P = pair<long long,int>;
25
    priority_queue<P, vector<P>, greater<P>> pq; // min-heap by distance
26
    pq.push({0, s});
27
28
    while (!pq.empty()) {
29
        auto [du, u] = pq.top(); pq.pop();
30
        if (du != dist[u]) continue; // stale entry (lazy deletion)
31
        for (auto [v, w] : g[u]) {
32
            if (dist[v] > dist[u] + w) {
33
                dist[v] = dist[u] + w;
34
                pq.push({dist[v], v}); // no decrease-key: push new better pair
35
            }
36
        }
37
    }
38
39
    for (int i = 0; i < n; ++i) {
40
        cout << (dist[i] == INF ? -1 : dist[i]) << (i+1==n?'\n':' ');
41
    }
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Node {
5
    int val;  // current value
6
    int i;    // which array
7
    int j;    // index within that array
8
};
9
10
struct Cmp {
11
    bool operator()(const Node &a, const Node &b) const {
12
        return a.val > b.val; // min-heap by value
13
    }
14
};
15
16
int main() {
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
20
    int K; cin >> K;
21
    vector<vector<int>> a(K);
22
    for (int i = 0; i < K; ++i) {
23
        int len; cin >> len;
24
        a[i].resize(len);
25
        for (int j = 0; j < len; ++j) cin >> a[i][j];
26
    }
27
28
    priority_queue<Node, vector<Node>, Cmp> pq;
29
    for (int i = 0; i < K; ++i) if (!a[i].empty()) pq.push({a[i][0], i, 0});
30
31
    vector<int> merged;
32
    while (!pq.empty()) {
33
        Node cur = pq.top(); pq.pop();
34
        merged.push_back(cur.val);
35
        int ni = cur.i, nj = cur.j + 1;
36
        if (nj < (int)a[ni].size()) {
37
            pq.push({a[ni][nj], ni, nj});
38
        }
39
    }
40
41
    for (int x : merged) cout << x << ' ';
42
    cout << '\n';
43
    return 0;
44
}
45

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Indexed Min-Priority Queue for keys associated with fixed indices [0..N-1].
5
// Supports: push(i, key), decreaseKey(i, newKey), contains(i), topIndex(), topKey(), pop().
6
// All heap operations are O(log n). This is handy for Dijkstra/Prim without lazy deletion.
7
8
struct IndexedMinPQ {
9
    int N;                       // maximum index
10
    vector<long long> key;       // key[i] is the current key for index i
11
    vector<int> pq;              // heap of indices: pq[pos] = index at heap position pos
12
    vector<int> pos;             // pos[i] = position of index i in heap, or -1 if not in heap
13
14
    IndexedMinPQ(int n) : N(n), key(n, LLONG_MAX), pos(n, -1) {}
15
16
    bool contains(int i) const { return pos[i] != -1; }
17
    bool empty() const { return pq.empty(); }
18
19
    bool lessIdx(int a, int b) const { return key[a] < key[b]; }
20
21
    void swapPos(int i, int j) {
22
        swap(pq[i], pq[j]);
23
        pos[pq[i]] = i; pos[pq[j]] = j;
24
    }
25
26
    void siftUp(int i) {
27
        while (i > 0) {
28
            int p = (i - 1) / 2;
29
            if (!lessIdx(pq[i], pq[p])) break;
30
            swapPos(i, p);
31
            i = p;
32
        }
33
    }
34
35
    void siftDown(int i) {
36
        int n = pq.size();
37
        while (true) {
38
            int l = 2*i + 1, r = 2*i + 2, best = i;
39
            if (l < n && lessIdx(pq[l], pq[best])) best = l;
40
            if (r < n && lessIdx(pq[r], pq[best])) best = r;
41
            if (best == i) break;
42
            swapPos(i, best);
43
            i = best;
44
        }
45
    }
46
47
    void push(int i, long long k) {
48
        if (contains(i)) {
49
            if (k < key[i]) { key[i] = k; siftUp(pos[i]); }
50
            else { key[i] = k; siftDown(pos[i]); }
51
            return;
52
        }
53
        key[i] = k;
54
        pq.push_back(i);
55
        pos[i] = (int)pq.size() - 1;
56
        siftUp(pos[i]);
57
    }
58
59
    void decreaseKey(int i, long long nk) {
60
        if (!contains(i) || nk >= key[i]) return; // no-op if not smaller
61
        key[i] = nk;
62
        siftUp(pos[i]);
63
    }
64
65
    int topIndex() const { return pq.empty() ? -1 : pq[0]; }
66
    long long topKey() const { return pq.empty() ? LLONG_MAX : key[pq[0]]; }
67
68
    pair<int,long long> pop() {
69
        int i = pq[0]; long long k = key[i];
70
        int last = pq.back(); pq.pop_back();
71
        pos[i] = -1;
72
        if (!pq.empty()) {
73
            pq[0] = last; pos[last] = 0; siftDown(0);
74
        }
75
        return {i, k};
76
    }
77
};
78
79
int main() {
80
    // Example: manage keys for indices 0..5
81
    IndexedMinPQ ipq(6);
82
    ipq.push(3, 50);
83
    ipq.push(1, 30);
84
    ipq.push(5, 40);
85
    ipq.decreaseKey(3, 10); // index 3 becomes best
86
    ipq.push(2, 20);
87
88
    while (!ipq.empty()) {
89
        auto [i, k] = ipq.pop();
90
        cout << "(idx=" << i << ", key=" << k << ") ";
91
    }
92
    cout << "\n";
93
    return 0;
94
}
95