C++: `std::priority_queue`

priority_queue.md

C++: std::priority_queue

Disclaimer: ChatGPT generated document.

std::priority_queue is a container adaptor in C++ that provides constant-time access to the largest (or highest priority) element. It’s implemented on top of another container (typically a std::vector) and uses a heap (by default, a max-heap) to maintain ordering.

It is ideal when you frequently insert items and need to efficiently retrieve (and remove) the highest-priority element.

---

📦 Overview

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Template Parameter	Description
T	The type of elements.
Container	The underlying container—defaults to std::vector<T>.
Compare	Comparator function—defaults to std::less<T>, making it a max-heap.

---

⚙️ Key Properties

• By default, the top element is the largest (std::less)
• Underlying container is a heap (std::make_heap, push_heap, pop_heap)
• Does not allow iteration—you only access top()
• Not stable (insertion order not preserved)
• Only supports:
  • push()
  • pop()
  • top()
  • empty()
  • size()
  • emplace() (since C++11)

---

⏱ Time Complexity

Operation	Complexity
push()	O(log N)
pop()	O(log N)
top()	O(1)
empty(), size()	O(1)

---

🔍 Basic Example

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
}

Output:

20 10 5

---

🧮 Custom Ordering

Min-heap (smallest element first)

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

---

Custom comparator (struct or lambda)

struct ComparePairs {
    bool operator()(const std::pair<int, int>& a,
                    const std::pair<int, int>& b) const {
        return a.second < b.second;  // higher 'second' = higher priority
    }
};

std::priority_queue<
    std::pair<int, int>,
    std::vector<std::pair<int, int>>,
    ComparePairs
> pq;

Or with a lambda:

auto cmp = [](int a, int b) { return a > b; }; // min-heap

std::priority_queue<
    int,
    std::vector<int>,
    decltype(cmp)
> pq(cmp);

---

🚀 Using emplace() (Efficiency Benefit)

pq.emplace(42);  // Constructs in-place, no copy or move

Faster than:

pq.push(42);     // Temporary created, then copied or moved

---

❌ Limitations

Limitation	Explanation
No iteration	You can't traverse elements in priority order.
No remove() except pop()	Only top removal is supported.
No change operations	Cannot modify priorities after insertion.
Not ordered internally	Only top() is guaranteed to be correct.

If you need sorted iteration, use something like std::multiset.

---

📚 Internal Mechanics

Internally, it maintains the heap using:

• push_heap() when adding
• pop_heap() when removing
• front() as the top

Memory layout is contiguous (same as std::vector).

---

🚦 When to Use

Use std::priority_queue when: ✔ You repeatedly insert items ✔ You always want the best candidate quickly ✔ You remove items often ✔ You don’t need iteration or re-prioritization

Typical use cases:

• Dijkstra's algorithm in graphs
• Scheduling systems
• Simulation engines
• A* search
• Event prioritization

---

📑 Summary Table

Feature	Description
Default structure	Max-heap
Supports	push, pop, top, emplace, size, empty
Best feature	Immediate access to highest priority
Limitations	No iteration, no arbitrary deletion
Time complexity	top() O(1), others O(log N)
Default container	std::vector
Thread-safety	No, like all STL containers

---

🏁 Final Example — With Custom Type

struct Task {
    int priority;
    std::string name;
};

struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority; // higher priority first
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, TaskCompare> pq;

    pq.emplace(Task{3, "Low"});
    pq.emplace(Task{10, "High"});
    pq.emplace(Task{5, "Medium"});

    while (!pq.empty()) {
        std::cout << pq.top().name << "\n";
        pq.pop();
    }
}

Output:

High
Medium
Low

---

💭 Final Thoughts

std::priority_queue is:

A fast, simple, heap-backed container ideally suited for priority-based processing.

It is not a general-purpose ordered structure—use it when only the top element matters.

If you ever need iteration or custom removal, consider std::multiset or <ranges>-powered containers.

---

Would you like: 👉 An example using std::priority_queue in a real algorithm (e.g. Dijkstra)? 👉 A thread-safe wrapper? 👉 Comparison against other containers like std::set or boost::heap?

Just say the word!