A min-heap is a binary tree such that:
1. The data contained in each node is less than (or equal to) the data in that node’s children.
2. The binary tree is complete
The C++ Standard Library consists of a container named priority_queue. A priority queue is technically a max-heap but it can be used to implement a min-heap by tweaking its constructor.
priority_queue<data_type,container_object,comparison>
The parameter comparison is used to order the heap. It may be a function pointer or function object capable of comparisons and must have two arguments.
The container object is by default a vector.
Example to implement a min-heap:
#include <queue> #include <iostream> using namespace std; struct comparator { bool operator()(int a, int b) { return a > b; } }; int main() { priority_queue<int, vector<int>, comparator> minHeap; minHeap.push(12); minHeap.push(8); minHeap.push(15); minHeap.push(2); minHeap.push(3); minHeap.push(9); while (!minHeap.empty()) { cout<<minHeap.top()<<" "; minHeap.pop(); } return 0; }
Output:
2 3 8 9 12 15
Note:
Instead of defining an explicit comparator structure, one can also use greater<data_type>
. This is defined in the functional package.
Example:
#include <queue> #include <iostream> using namespace std; int main() { priority_queue<int, vector<int>, greater<int> > minHeap; minHeap.push(12); minHeap.push(8); minHeap.push(15); minHeap.push(2); while (!minHeap.empty()) { cout<<minHeap.top()<<" "; minHeap.pop(); } return 0; }
Output:
2 8 12 15