YouTipCpp Libs Priority_Queue
# C++ Standard Library: ``
In C++, `std::priority_queue` is a container adapter provided by the Standard Template Library (STL) under the `` header. It is designed to model a queue where elements are ordered by priority rather than their insertion order.
A priority queue allows for fast $O(1)$ access to the element with the highest (or lowest) priority, while insertions and deletions are performed in logarithmic time $O(\log n)$.
---
## Key Characteristics
* **Heap-Based Implementation:** By default, `std::priority_queue` is implemented as a **max-heap**. This means the element at the top of the queue always holds the largest value according to the comparison criteria.
* **Container Adapter:** It is not a standalone container but an adapter that wraps around an underlying sequential container (such as `std::vector` or `std::deque`) and provides a heap-based interface.
* **No Iterators:** It does not support iterators or random access. You can only access the top element.
---
## Syntax and Template Parameters
To use `std::priority_queue`, you must include the `` header:
```cpp
#include
```
### Template Definition
```cpp
template<
class T,
class Container = std::vector,
class Compare = std::less
> class priority_queue;
```
* **`T`**: The type of the elements stored in the queue.
* **`Container`**: The underlying container type used to store the elements. It must support random-access iterators and front/back operations (typically `std::vector` or `std::deque`). Defaults to `std::vector`.
* **`Compare`**: A binary predicate that takes two arguments of the element type and returns a `bool`. Defaults to `std::less`, which creates a **max-heap**.
### Basic Declarations
```cpp
// 1. Default Max-Heap (Highest value at the top)
std::priority_queue max_pq;
// 2. Min-Heap using std::greater (Lowest value at the top)
std::priority_queue, std::greater> min_pq;
// 3. Custom Type with Custom Comparator Struct
struct CustomCompare {
bool operator()(int a, int b) {
return a > b; // Returns true if 'a' should have lower priority than 'b' (Min-Heap behavior)
}
};
std::priority_queue, CustomCompare> custom_pq;
```
---
## Common Member Functions
| Member Function | Description | Time Complexity |
| :--- | :--- | :--- |
| `top()` | Returns a reference to the top element (highest priority) without removing it. | $O(1)$ |
| `push(const T& val)` | Inserts a new element into the priority queue and reorders the heap. | $O(\log n)$ |
| `emplace(Args&&... args)` | Constructs an element in-place directly inside the container. | $O(\log n)$ |
| `pop()` | Removes the top element from the priority queue. | $O(\log n)$ |
| `empty()` | Checks whether the priority queue is empty. | $O(1)$ |
| `size()` | Returns the number of elements in the priority queue. | $O(1)$ |
---
## Code Examples
### Example 1: Default Max-Heap
The following example demonstrates how to create a default max-heap, insert elements, and retrieve them in descending order.
```cpp
#include
#include
int main() {
// Create a priority queue of integers (default: Max-Heap)
std::priority_queue pq;
// Insert elements
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
// Retrieve and print elements
std::cout << "Elements in Max-Heap (highest to lowest):" << std::endl;
while (!pq.empty()) {
std::cout << pq.top() << std::endl; // Access the top element
pq.pop(); // Remove the top element
}
return 0;
}
```
**Output:**
```text
Elements in Max-Heap (highest to lowest):
50
30
20
10
```
---
### Example 2: Custom Priority (Min-Heap)
If you need a min-heap (where the smallest value is always at the top), you can pass `std::greater` as the third template argument, or define a custom comparator struct.
```cpp
#include
#include
#include
// Custom comparator struct
struct Compare {
bool operator()(int a, int b) {
return a > b; // Defines a Min-Heap
}
};
int main() {
// Create a priority queue with a custom comparator for a Min-Heap
std::priority_queue, Compare> pq_min;
// Insert elements
pq_min.push(30);
pq_min.push(10);
pq_min.push(50);
pq_min.push(20);
// Retrieve and print elements
std::cout << "Elements in Min-Heap (lowest to highest):" << std::endl;
while (!pq_min.empty()) {
std::cout << pq_min.top() << std::endl; // Access the top element
pq_min.pop(); // Remove the top element
}
return 0;
}
```
**Output:**
```text
Elements in Min-Heap (lowest to highest):
10
20
30
50
```
---
## Advanced Usage: Priority Queue of Custom Objects
When working with custom classes or structs, you must define how they are compared. You can do this by overloading the `<` operator inside the struct or by passing a custom comparator class.
```cpp
#include
#include
#include
#include
struct Task {
int priority;
std::string description;
// Overload the '<' operator to define priority.
// Note: In std::priority_queue, the element that evaluates to "less" is placed lower in the heap.
// Therefore, to make higher priority numbers come first, we use '<'.
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
int main() {
std::priority_queue task_queue;
task_queue.push({2, "Write documentation"});
task_queue.push({5, "Fix critical production bug"});
task_queue.push({1, "Clean up workspace"});
task_queue.push({3, "Refactor legacy code"});
std::cout << "Executing tasks based on priority:" << std::endl;
while (!task_queue.empty()) {
Task current = task_queue.top();
std::cout << "[" << current.priority << "] " << current.description << std::endl;
task_queue.pop();
}
return 0;
}
```
**Output:**
```text
Executing tasks based on priority:
Fix critical production bug
Refactor legacy code
Write documentation
Clean up workspace
```
---
## Considerations & Best Practices
1. **No Iteration Support:** You cannot iterate through a `std::priority_queue` using a `for` loop or iterators. If you need to inspect all elements without destroying the queue, consider using `std::vector` with `std::make_heap`, `std::push_heap`, and `std::pop_heap` algorithms instead.
2. **Performance:**
* `top()` is $O(1)$.
* `push()` and `pop()` are $O(\log n)$.
* Building a priority queue of size $n$ from an existing container using the constructor takes $O(n)$ time, which is more efficient than pushing elements one by one ($O(n \log n)$).
3. **Memory Overhead:** Since it is typically backed by `std::vector`, it inherits its dynamic resizing behavior. Ensure you use `emplace()` instead of `push()` when inserting temporary objects to avoid unnecessary copy or move operations.