C++ Standard Template Library (STL) – [Heap]

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:

https://ideone.com/L5dtfk

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:

https://ideone.com/2lOBp4

Leave a Reply

Your email address will not be published.