C++ Priority Queue Solutions: Greedy Algorithms and Heap Examples

C++ Priority Queue Examples

The following code samples demonstrate how to use the priority_queue container from the C++ Standard Template Library (STL) to solve common greedy and heap-based problems.

1. Minimum Cost to Merge Ropes (Huffman-style)

This program repeatedly merges the two smallest values using a min-heap and accumulates the total cost.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
int n;
cin >> n;

priority_queue<long long, vector<long long>, greater<long long>> q;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
q.push(x);
}

long long ans = 0;
while (q.size() > 1) {
long long a = q.top(); q.pop();
long long b = q.top(); q.pop();
ans += a + b;
q.push(a + b);
}

cout << ans << endl;
return 0;
}

2. Final Remaining Value After Pairwise Differences

This program uses a max-heap to repeatedly replace the two largest values with their difference, returning the last remaining value (or 0 if none remains).

#include <iostream>
#include <queue>
using namespace std;

int main() {
int n;
cin >> n;

priority_queue<long long> q;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
q.push(x);
}

while (q.size() > 1) {
long long y = q.top(); q.pop();
long long x = q.top(); q.pop();
if (y != x) {
q.push(y - x);
}
}

if (q.empty()) cout << 0 << endl;
else cout << q.top() << endl;
return 0;
}

3. Maximum Sum by Repeatedly Taking and Decrementing the Top Element

This program takes the largest element x times, adds it to the answer, and pushes back the decremented value when it is greater than 1.

#include <iostream>
#include <queue>
using namespace std;

int main() {
int n, x;
cin >> n >> x;

priority_queue<int> q;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
q.push(a);
}

long long ans = 0;
for (int i = 0; i < x; i++) {
int k = q.top();
q.pop();
ans += k;
if (k > 1) {
q.push(k - 1);
}
}

cout << ans << endl;
return 0;
}

4. Counting Combine Operations Until All Values Exceed a Threshold

This program combines the two smallest values as a + 2b until the minimum exceeds m, using a min-heap with fast I/O.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n;
long long m;
cin >> n >> m;

priority_queue<long long, vector<long long>, greater<long long>> q;
for (int i = 0; i < n; i++) {
long long d;
cin >> d;
q.push(d);
}

int cnt = 0;
while (q.top() <= m) {
if (q.size() < 2) {
cout << -1 << endl;
return 0;
}
long long a = q.top(); q.pop();
long long b = q.top(); q.pop();
q.push(a + 2 * b);
cnt++;
}

cout << cnt << endl;
return 0;
}

5. Sliding Sum of the Top K Values (Insert and Query)

This program maintains the sum of the k largest inserted values using a min-heap of size k, answering each query in order.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int q, k;
cin >> q >> k;

priority_queue<long long, vector<long long>, greater<long long>> h;
long long sum = 0;

for (int i = 0; i < q; i++) {
string s;
cin >> s;
if (s ==