The Heap data structure is an array that can be viewed as a complete Binary Tree. Each node in the tree corresponds to an element of the array A[]. We already discussed Heap data structure in this – post.

However in this post we would learn about, how to build min/max Heaps using STL. For using vectors as Heap, we need to include the <algorithm> header file.
Max-Heap
vector<int> H = {20, 10, 70, 30}; Create (H) 1. make_heap(H.begin(), H.end()); Insert (H, x) 1. H.push_back(x) 2. push_heap (H.begin(), H.end()) Max (H) 1. return H.front() Extract-Max (H) 1. x = H.front() 2. pop_heap (H.begin(), H.end()) 3. H.pop_back() 3. return x
Code Implementation
//
// main.cpp
// Max Heap
//
// Created by Himanshu on 02/10/21.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
vector<int> maxHeap = {30, 100, 25, 40};
make_heap(maxHeap.begin(), maxHeap.end());
cout<<"Insert H(x) {20, 70}"<<endl;
maxHeap.push_back(20);
push_heap(maxHeap.begin(), maxHeap.end());
maxHeap.push_back(70);
push_heap(maxHeap.begin(), maxHeap.end());
cout<<"Maximum Element (H)"<<endl;
cout<<maxHeap.front()<<endl;
cout<<"Maximum Element (H) after Extract-Max (H)"<<endl;
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
cout<<maxHeap.front()<<endl;
cout <<"Extracting out elements..."<<endl;
while (!maxHeap.empty()) {
cout<< maxHeap.front()<<" ";
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
}
cout<<endl;
if (maxHeap.empty()) {
cout<<"Heap is empty"<<endl;
} else {
cout<<"Heap is not empty"<<endl;
}
return 0;
}
Output
Insert H(x) {20, 70} Maximum Element (H) 100 Maximum Element (H) after Extract-Max (H) 70 Extracting out elements... 70 40 30 25 20 Heap is empty
Here’s a working example:
Min-Heap
For using min-heap, we need to add an extra parameter ie. greater<int>() in heap methods.
vector<int> H = {20, 10, 70, 30}; Create (H) 1. make_heap(H.begin(), H.end(), greater<int>()); Insert (H, x) 1. H.push_back(x) 2. push_heap (H.begin(), H.end(), greater<int>()) Min (Q) 1. return H.top() Extract-Min (H) 1. x = H.top() 2. pop_heap (H.begin(), H.end(), greater<int>()) 3. H.pop_back() 3. return x
Code Implementation
//
// main.cpp
// Min Heap
//
// Created by Himanshu on 02/10/21.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
vector<int> minHeap = {30, 100, 25, 40};
make_heap(minHeap.begin(), minHeap.end(), greater<int>());
cout<<"Insert H(x) {20, 70}"<<endl;
minHeap.push_back(20);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.push_back(70);
push_heap(minHeap.begin(), minHeap.end(), greater<int>());
cout<<"Minimum Element (H)"<<endl;
cout<<minHeap.front()<<endl;
cout<<"Minimum Element (H) after Extract-Min (H)"<<endl;
pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.pop_back();
cout<<minHeap.front()<<endl;
cout <<"Extracting out elements..."<<endl;
while (!minHeap.empty()) {
cout<< minHeap.front()<<" ";
pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
minHeap.pop_back();
}
cout<<endl;
if (minHeap.empty()) {
cout<<"Heap is empty"<<endl;
} else {
cout<<"Heap is not empty"<<endl;
}
return 0;
}
Output
Insert H(x) {20, 70} Minimum Element (H) 20 Minimum Element (H) after Extract-Min (H) 25 Extracting out elements... 25 30 40 70 100 Heap is empty
Here’s a working example: