Is there an easy way to make a min heap in C++?

Question

I'm very new to C++, and I was wondering if there was a way to make a min heap in C++ from the standard library.

Plutocrat

You ask questions and accept none. Is this behavior by habit or choice? – Heathenize

Answer 1

Use make_heap() and friends, defined in <algorithm>, or use priority_queue, defined in <queue>. The priority_queue uses make_heap and friends underneath.

#include <queue> // functional,iostream,ctime,cstdlib
using namespace std;

int main(int argc, char* argv[])
{
    srand(time(0));
    priority_queue<int,vector<int>,greater<int> > q;
    for( int i = 0; i != 10; ++i ) q.push(rand()%10);
    cout << "Min-heap, popped one by one: ";
    while( ! q.empty() ) {
        cout << q.top() << ' ';  // 0 3 3 3 4 5 5 6 8 9
        q.pop();
    }
    cout << endl;
    return 0;
}

Sinistrorse

Answer 2

You can use std::make_heap, std::push_heap, and others directly, or you can use a std::priority_queue built on a std::vector or similar.

The std::*_heap methods are in <algorithm>, and the std::priority_queue template is in <queue>.

Promotive

oh so if i popped from the priority_queue in c++ i'd get the min value? – Plutocrat

To clarify further, priority_queue's whole template accepts a container type, which defaults to vector<T>. Any container which supports random iteration and push_back will suffice, however. – Promotive

If say I have priority_queue<Node>, how do I set the sorting function of the queue? – Plutocrat

You would use the full template; in paraphrase, priority_queue<T, container, comp>. This question, and your original, honestly, is something you should be able to google yourself and find a satisfactory answer. – Promotive

@Alex: Or simply declare Node::operator<. – Diandiana

To clarify more, priority_queue is a max-heap, if you want a min-heap, you have to use std::greater as a comparator. See Wilhelm's answer. – Poetry

Answer 3

You can use the std::priority_queue defined in with std::greater defined in .

For example:

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

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap();
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);
minHeap.push(2);
minHeap.push(4);

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

This will print:

1
2
3
4
5

Condescend