Priority Queue

In this article we will see different way to use max, min heap using priority_queue in cpp. By default, priority_queue creates a maxHeap.

1. Max Heap
2. Min Heap
3. Max Heap with pair<int, int>
4. Min Heap with pair<int, int>
5. Using Priority queue with Custom Types
6. MaxHeap with Struct
7. MinHeap with Structs
8. General Rule for Priority_queue

Max Heap

    priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(15);

    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    // Output: 15 10 5

Min Heap

To implement a minHeap, we need to tell compiler to change default comparison order, which can be done via passing a different comparator.

    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(15);

    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    // Output: 5 10 15

That was basic for ints, now lets say we want to create for a pair<int, int>. For the pair, default declaration works as a maxHeap based on first value.

Max Heap with pair<int, int>

    priority_queue<pair<int, int>> maxPQ;
    maxPQ.push({2, 100});
    maxPQ.push({1, 200});
    maxPQ.push({3, 50});

    while (!maxPQ.empty()) {
        auto p = maxPQ.top();
        cout << "(" << p.first << ", " << p.second << ") ";
        maxPQ.pop();
    }
    // Output: (3, 50) (2, 100) (1, 200)

Min Heap with pair<int, int>

Just like, minHeap with regular int, for pair, we also need to pass custom comparator function. In this case we can still use std::greater<>

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minPQ;
    minPQ.push({2, 100});
    minPQ.push({1, 200});
    minPQ.push({3, 50});

    while (!minPQ.empty()) {
        auto p = minPQ.top();
        cout << "(" << p.first << ", " << p.second << ") ";
        minPQ.pop();
    }
    // Output: (1, 200) (2, 100) (3, 50)

Using Priority queue with Custom Types

We can use custom types with priority_queue as well. Consider a tree problem, where we want a maxHeap based on level and values. At level 1, if we see multiple nodes like 10,20,5,30. These should be also be stored a maxHeap. So, we will have to write a custom comparion operator for arranging elements in this order. This is how we can write a custom method for comparison

MaxHeap with Struct

// Custom comparator for max heap with tie-breaking on value
struct Compare {
    bool operator()(const Node& a, const Node& b) {
        if (a.level == b.level)
            return a.value < b.value;  // higher value comes first
        return a.level < b.level;      // higher level comes first
    }
};

Complete code for this

struct Node {
    int level;
    int value;
};

// Custom comparator for max heap with tie-breaking on value
struct Compare {
    bool operator()(const Node& a, const Node& b) {
        if (a.level == b.level)
            return a.value < b.value;  // higher value comes first
        return a.level < b.level;      // higher level comes first
    }
};

int main() {
    priority_queue<Node, vector<Node>, Compare> pq;

    pq.push({2, 100});
    pq.push({3, 50});
    pq.push({3, 200});
    pq.push({1, 500});

    while (!pq.empty()) {
        Node top = pq.top();
        cout << "Level: " << top.level << ", Value: " << top.value << endl;
        pq.pop();
    }

    // Output:
    // Level: 3, Value: 200
    // Level: 3, Value: 50
    // Level: 2, Value: 100
    // Level: 1, Value: 500
}

We can follow above to create a minHeap for structs as well, the only change will be in the Comp function.

MinHeap with Structs

struct Node {
    int level;
    int value;
};

// Custom comparator for min heap: lower level first, then lower value
struct CompareMin {
    bool operator()(const Node& a, const Node& b) {
        if (a.level == b.level)
            return a.value > b.value;  // lower value first
        return a.level > b.level;      // lower level first
    }
};

int main() {
    priority_queue<Node, vector<Node>, CompareMin> pq;

    pq.push({2, 100});
    pq.push({3, 50});
    pq.push({3, 200});
    pq.push({1, 500});

    while (!pq.empty()) {
        Node top = pq.top();
        cout << "Level: " << top.level << ", Value: " << top.value << endl;
        pq.pop();
    }

    // Output:
    // Level: 1, Value: 500
    // Level: 2, Value: 100
    // Level: 3, Value: 50
    // Level: 3, Value: 200
}

General Rule for Priority_queue

The priority_queue is internally a max heap by default, and the comparator works like std::less — that is, the top of the queue is the greatest element according to the comparator.

But when you pass a custom comparator, the semantics are:

bool operator()(const T& a, const T& b)
returns true if a should come after b in the priority order.

Which means:

• Returning true → a has lower priority than b
• Returning false → a has higher or equal priority to b

Heap Type	Logic	Meaning
Max	a.attr < b.attr	Higher value = higher priority
Min	a.attr > b.attr	Lower value = higher priority

Let’s say we have 2 numbers 5, 10, so a= 5, b = 10, this comp gives , 5 < 10 true, which say means 5 should come after 10 (cool). Let’s reverse the numbers (just to validate if order in array matters or not) order a = 10, b = 5, 10 < 5 false, which 10 can’t come after 5, so it comes before. So, evenutally we have 10, 5 following a maxHeap.