std::priority_queueis a priority queue provided by C++ STL, which is a maximum heap (by default) that can be used to efficiently obtain the current largest (or minimum) element.
1. Basic usage
(1) Header file
To usestd::priority_queue, need to include:
#include <queue> #include <vector> #include <iostream>
(2) Default (maximum heap)
By default,std::priority_queueIt is the largest heap, that is, the top of the heap is the largest element:
std::priority_queue<int> pq; // The default is the maximum heap
Example:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
(10);
(30);
(20);
std::cout << "Heap Top Element:" << () << std::endl; // Output 30
(); // Remove 30 std::cout << "New top:" << () << std::endl; // Output 20
return 0;
}
✅ Features
-
push()Insert elements to automatically maintain the maximum heap. -
top()Get the current largest element (top of heap). -
pop()Remove the heap top element (but not return it). -
size()Get the queue size. -
empty()Check whether the queue is empty.
2. Customize the minimum heap
If you want to implement the minimum heap (the top of the heap is the smallest element), you can usestd::greater<T>：
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
Example:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
pq_min.push(10);
pq_min.push(30);
pq_min.push(20);
std::cout << "Heap Top Element:" << pq_min.top() << std::endl; // Output 10
pq_min.pop();
std::cout << "New top:" << pq_min.top() << std::endl; // Output 20
return 0;
}
✅ Key points
-
std::greater<int>makepriority_queueBecome the smallest pile.
3. Custom comparison function (struct/fancy function)
(1) Structural imitation function
struct Compare {
bool operator()(int a, int b) {
return a > b; // Minimum heap (a > b means a below b) }
};
std::priority_queue<int, std::vector<int>, Compare> pq;
Example:
#include <iostream>
#include <queue>
struct Compare {
bool operator()(int a, int b) {
return a > b; // Make small elements have high priority }
};
int main() {
std::priority_queue<int, std::vector<int>, Compare> pq;
(10);
(30);
(20);
std::cout << "Heap Top Element:" << () << std::endl; // Output 10
();
std::cout << "New top:" << () << std::endl; // Output 20
return 0;
}
✅ Advantages
- Suitable for complex data structures (e.g.
struct）。 - Allows flexibility to define priorities.
4. Processing structure type
ifpriority_queueThe storage is a custom structure and comparison rules are required.
(1) Task Scheduling Sort by Weight
#include <iostream>
#include <queue>
struct Task {
int id;
int priority;
// Overload operator, used for maximum heap (high priority) bool operator<(const Task& other) const {
return priority < ; // High priority ranking in front }
};
int main() {
std::priority_queue<Task> pq;
({1, 3});
({2, 5});
({3, 1});
std::cout << "Highest priority task ID:" << ().id << std::endl; // Output 2
();
std::cout << "New highest priority task ID:" << ().id << std::endl; // Output 1
return 0;
}
✅ Features
- The default is the maximum heap, so
operator<Defined as the one with a small priority is below.
(2) Use custom comparison functions
If it cannot be modifiedstruct, you can use the external comparison function:
struct CompareTask {
bool operator()(const Task& a, const Task& b) {
return > ; // Minimum stack }
};
std::priority_queue<Task, std::vector<Task>, CompareTask> pq;
Complete example:
#include <iostream>
#include <queue>
struct Task {
int id;
int priority;
};
// Make priority_queue the minimum heapstruct CompareTask {
bool operator()(const Task& a, const Task& b) {
return > ; // Small priority tasks }
};
int main() {
std::priority_queue<Task, std::vector<Task>, CompareTask> pq;
({1, 3});
({2, 5});
({3, 1});
std::cout << "Highest priority task ID:" << ().id << std::endl; // Output 3
();
std::cout << "New highest priority task ID:" << ().id << std::endl; // Output 1
return 0;
}
✅ Applicable scenarios
- Priority queue scheduling algorithm
- Event-driven simulation
- A Search (Shortest Path Algorithm)*
5. priority_queue applicable scenarios
| Application scenarios | usage |
|---|---|
| Maximum heap (default) | std::priority_queue<int> |
| Minimum stack | std::priority_queue<int, std::vector<int>, std::greater<int>> |
| Storage structure (maximum heap) | Structural heavy load |
| Storage structure (minimum heap) | std::greater<> or custom Compare |
| K Large/Small Elements | Maintain a heap of size K |
| Dijkstra / A Search* | Combined with std::pair<int, int> for path calculation |
6. Classic application examples
(1) Find the first K largest elements
#include <iostream>
#include <queue>
#include <vector>
void findTopK(std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // Minimum stack
for (int num : nums) {
(num);
if (() > k) (); // Only k maximum values are retained }
std::cout << "forward " << k << "The biggest element:" << () << std::endl;
}
int main() {
std::vector<int> nums = {3, 1, 5, 12, 2, 11};
findTopK(nums, 3); // Output 5}
✅ Complexity:O(N log K)
Summarize
-
std::priority_queueThe default is the maximum heap, which can be usedstd::greater<>Implement the minimum heap. - When storing structures, overloading can be used
<Operator or custom comparator. - Suitable for scenarios such as task scheduling, path search (Dijkstra/A)*.
This is the article about the use of std::priority_queue in C++. For more information about using std::priority_queue in C++, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!