In C++ STL we have priority_queue, which is a Max heap. To use the priority_queue as min heap, we need to tweak the comparator operator used by the library.
In Max Heap comparator should return true if a < b but for Min heap it should return false.
#include <queue>
#include <iostream>
using namespace std;
struct comparator {
bool operator()(int i, int j) {
return i > j;
}
};
int main(int argc, char const *argv[])
{
priority_queue<int, std::vector<int>, comparator> minHeap;
minHeap.push(10);
minHeap.push(5);
minHeap.push(12);
minHeap.push(3);
minHeap.push(3);
minHeap.push(4);
while (!minHeap.empty()) {
cout << minHeap.top() << " ";
minHeap.pop();
}
return 0;
}
Output: 3 3 4 5 10 12
Now we will consider push_heap() and pop_heap from algorithms package to maintain heap in a vector. This is little bit cumbersome as we have to define our own push and pop functions.
Here is the example of a min heap. For max heap just remove the greater() functions in the code.
#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
using namespace std;
void Push(vector<int>& heap, int val) {
heap.push_back(val);
push_heap(heap.begin(), heap.end(), greater<int>());
}
int Pop(vector<int>& heap) {
int val = heap.front();
//This operation will move the smallest element to the end of the vector
pop_heap(heap.begin(), heap.end(), greater<int>());
//Remove the last element from vector, which is the smallest element
heap.pop_back();
return val;
}
int main() {
vector<int> heap;
Push(heap, 1);
Push(heap, 7);
Push(heap, 5);
while (!heap.empty()) {
cout << Pop(heap) << endl;
}
return 0;
}
greater() : Is same as the overloaded () operator in Comparator structure defined above. This is defined in functional package, so we can use it without defining our own. This makes our life, is not it 🙂
push_heap() : This is function is responsible to rearrange the elements in the vector so that they satisfy the heap property
pop_heap(): This function move the top element to back of the vector and rearrages the elements to satisfy heap property.
What if we want to maintain a heap of object. In that we can’t use functional(), we need to define our own comparator structure for comparison of objects. We need to define the comparator structure for min and max heap.
CodeConnect 