std::priority_queue
Heap-based priority queue
Interview Relevant: Heap problems
Priority Queue
Heap-based container. O(log n) push/pop, O(1) top.
Code Examples
Priority queue for heap operations.
cpp
1#include <queue>
2
3// Max heap (default)
4priority_queue<int> maxHeap;
5maxHeap.push(3);
6maxHeap.push(1);
7maxHeap.push(4);
8cout << maxHeap.top(); // 4 (largest)
9maxHeap.pop();
10
11// Min heap
12priority_queue<int, vector<int>, greater<int>> minHeap;
13minHeap.push(3);
14minHeap.push(1);
15minHeap.push(4);
16cout << minHeap.top(); // 1 (smallest)
17
18// Custom comparator
19struct Compare {
20 bool operator()(pair<int,int>& a, pair<int,int>& b) {
21 return a.second > b.second; // Min by second element
22 }
23};
24priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;
25
26// K largest elements
27vector<int> kLargest(vector<int>& nums, int k) {
28 priority_queue<int, vector<int>, greater<int>> minHeap;
29 for (int n : nums) {
30 minHeap.push(n);
31 if (minHeap.size() > k) minHeap.pop();
32 }
33 vector<int> result;
34 while (!minHeap.empty()) {
35 result.push_back(minHeap.top());
36 minHeap.pop();
37 }
38 return result;
39}