How to Create Min Heap Using priority_queue in C++

In C++, to create a min heap using priority_queue, you need to specify a custom comparator like std::greater<Type> as the third template argument. This changes the default max heap behavior to min heap, so the smallest element is always on top.

Syntax

The priority_queue template has three parameters: the data type, the container type (usually std::vector), and the comparator. To create a min heap, use std::greater<Type> as the comparator.

• Type: The data type stored in the heap.
• Container: The underlying container, default is std::vector<Type>.
• Compare: The comparison function object, default is std::less<Type> (max heap).

cpp

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

Example

This example shows how to create a min heap of integers using priority_queue with std::greater<int>. It inserts some numbers and prints them in ascending order by popping from the heap.

cpp

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

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

Output

5 10 20 30 

Common Pitfalls

Many beginners forget to specify the comparator and get a max heap instead of a min heap. Another common mistake is mixing up std::less and std::greater. Also, ensure the container type matches the comparator.

cpp

#include <queue>
#include <vector>

// Wrong: creates max heap (default)
std::priority_queue<int> maxHeap;

// Correct: creates min heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

Quick Reference

Component	Description	Example
Type	Data type stored in the heap	int
Container	Underlying container type	std::vector
Compare	Comparator to define heap order	std::greater for min heap
Default Compare	Default comparator for max heap	std::less

Key Takeaways

Use std::greater as the comparator in priority_queue to create a min heap.

The default priority_queue creates a max heap with std::less.

Always specify the container type (usually std::vector) when changing the comparator.

Popping from a min heap returns elements in ascending order.

Mixing up comparators leads to unexpected heap behavior.