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 will 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
Time Complexity
- Create (H) procedure: running time O(n)
- Insert (H, x) procedure: running time O(logn)
- Max (H) procedure: running time O(1)
- Extract-Max (H) procedure: running time O(logn)
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: Ideone
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 (H)
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
Time Complexity
- Create (H) procedure: running time O(n)
- Insert (H, x) procedure: running time O(logn)
- Min (H) procedure: running time O(1)
- Extract-Min (H) procedure: running time O(logn)
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: Ideone