Wait, what actually is a priority queue and when should I use it over a normal queue?

Think of a standard std::queue as a line at a coffee shop: first come, first served. A std::priority_queue is more like an emergency room. It doesn't matter when you arrived; if someone comes in with a life-threatening injury, they jump to the front of the line.

In C++, this is implemented as a max-heap by default. This means the "largest" element—according to whatever comparison logic is being used—is always sitting at the top. I use these all the time when I'm dealing with things like task schedulers or pathfinding algorithms where I need to constantly grab the "most important" item without sorting the entire list every single time.

#include <iostream>
#include <queue>
#include <string>

struct Task {
    int priority;
    std::string description;

    // We overload the < operator because priority_queue uses it to order elements
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

int main() {
    std::priority_queue<Task> todoList;

    todoList.push({1, "Check email"});
    todoList.push({10, "Fix production crash!"});
    todoList.push({5, "Write documentation"});

    // Even though "Fix production crash" was added second, it comes out first.
    std::cout << "Handling: " << todoList.top().description << std::endl; 
    return 0;
}

Why is my priority queue giving me the largest number, and how do I make it a min-heap instead?

This is the single most confusing part of the STL priority queue. By default, it uses std::less<T>, which sounds like it should give you the smallest item, but it actually creates a max-heap. I've lost plenty of hours to this confusion in the past.

If you want a min-heap (where the smallest number is at the top), you have to change the template arguments. You need to specify the underlying container (usually a std::vector) and then pass std::greater<T> as the comparison functional. It feels verbose, but that's just how the template is structured.

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // Syntax: priority_queue<Type, Container, Comparison>
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(50);
    minHeap.push(10);
    minHeap.push(100);

    // Now, the smallest element (10) is at the top.
    std::cout << "Smallest element: " << minHeap.top() << std::endl;
    return 0;
}

I see make_heap and push_heap in the documentation. Are those just different ways to do the same thing?

Not exactly. std::priority_queue is a container adapter. It wraps around another container to restrict its interface so you can only interact with the top element. It's a "black box" for the sake of safety and intent.

The functions like std::make_heap, std::push_heap, and std::pop_heap are raw algorithms that work on any random-access iterator (like a std::vector). You use these when you need more flexibility. For example, if you need to iterate through all the elements in the heap without removing them, or if you want to transform an existing vector into a heap in-place without copying the data into a new object.

My rule of thumb: Use std::priority_queue 95% of the time. Only dive into the <algorithm> heap functions if you have a very specific reason to manipulate the underlying memory layout of your data.

📋 Practical Task

Implement a Dijkstra-style "Shortest Path" Node Processor

In graph algorithms, we often need to keep track of the "closest" node to visit next. Your task is to build a simple node processor that simulates this behavior.

• Create a struct Node that contains an id (int) and a distance (double).
• Implement a custom comparison operator or a comparator struct so that a std::priority_queue treats the node with the smallest distance as the highest priority.
• Create a std::vector of several Nodes with random distances.
• Push all these nodes into your priority queue.
• Pop and print the nodes one by one. If your implementation is correct, the nodes should print in ascending order of their distance, regardless of the order they were added.