Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is min heap in C++?
2.1.
Min Heap
3.
Min Heap Implementation in C++
3.1.
C++
4.
Min Heap C++ Representation
5.
Important Methods of MinHeap
6.
Another method for making min-heap using default priority_queue
6.1.
C++
7.
Properties of Binary Heap
8.
Frequently Asked Questions
8.1.
How min heap is implemented?
8.2.
Does C++ have a max heap?
8.3.
Why do we use heap in C++?
8.4.
Is min heap a priority queue?
8.5.
How do you create a min heap in C++?
9.
Conclusion
Last Updated: Jul 3, 2024
Easy

Implement min heap in C++

Author Anant Dhakad
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Min heap comes in handy whenever we want a data structure for handling insertion, deletion and finding the minimum in O(Logn). In this blog, we will learn the implementation of Min Heap in C++.implement min-heap in c++

What is min heap in C++?

In C++, a min-heap is a specialized binary tree-based data structure that satisfies the heap property. Specifically, in a min heap, for any given node iii, the value of the node must be less than or equal to the values of its children. This property ensures that the smallest element (the minimum) is always at the root of the heap.

A heap can be represented as a complete binary tree, where all levels are fully filled except possibly the last level, which is filled from left to right.

Min Heap

  • The top node/root node will always have a minimum value.
  • Extracting an element from the priority queue will always give the minimum among all the current values stored in the heap.
  • Inserting and deletion operation takes time.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Min Heap Implementation in C++

  • C++

C++

#include<bits/stdc++.h>
using namespace std;

// A class for Min Heap
class MinHeap{
   int *heap_array; // pointer to array of elements in heap
   int capacity; // maximum possible size of min heap
   int heap_size; // Current number of elements in min heap

public:
   // Constructor: Initialise a capacity and heap_array;
   MinHeap(int capacity){
       this->heap_size = 0;
       this->capacity = capacity;
       this->heap_array = new int[capacity];
   }

   // method to heapify a subtree with the root at given index i
   void MinHeapify(int i){
       /* A recursive method to heapify 'heap_array' */
       int l = left(i);
       int r = right(i);

       int smallest = i;
       if (l < heap_size && heap_array[l] < heap_array[i])
           smallest = l;
       if (r < heap_size && heap_array[r] < heap_array[smallest])
           smallest = r;

       if (smallest != i){
           swap(heap_array[i], heap_array[smallest]);
           MinHeapify(smallest);
       }
   }

   // method to get index of parent of node at index i
   int parent(int i){ return (i-1)/2; }

   // method to get index of left child of node at index i
   int left(int i){ return (2*i + 1); }

   // method to get index of right child of node at index i
   int right(int i){ return (2*i + 2); }

   // method to remove minimum element (or root) from min heap
   int extractMin(){
       if (heap_size <= 0)
           return INT_MAX;
       if (heap_size == 1){
           heap_size--;
           return heap_array[0];
       }

       // remove the minimum value from the heap.
       int root = heap_array[0];
       heap_array[0] = heap_array[heap_size-1];
       heap_size--;
       MinHeapify(0);

       return root;
   }

   // method to decrease key value of key at index i to new_val
   void decreaseKey(int i, int new_val){
       heap_array[i] = new_val;
       while (i != 0 && heap_array[parent(i)] > heap_array[i]){
           swap(heap_array[i], heap_array[parent(i)]);
           i = parent(i);
       }
   }

   // Returns the minimum key (key at root) from min heap
   int getMin(){ return heap_array[0]; }

   // method deletes key at index i
   // (It first reduced value to minus infinite, then calls extractMin() )
   void deleteKey(int i){
       decreaseKey(i, INT_MIN);
       extractMin();
   }

   // method to inserts a new key 'k'
   void insertKey(int k){
       if (heap_size == capacity){
           cout << "\nOverflow: Could not insertKey\n";
           return;
       }

       // Inserting the new key at the end
       int i = heap_size;
       heap_array[heap_size++] = k;

       while (i != 0 && heap_array[parent(i)] > heap_array[i]){
           swap(heap_array[i], heap_array[parent(i)]);
           i = parent(i);
       }
   }
};

// Driver program to test above functions
int main(){
   MinHeap h(11);
   h.insertKey(15);
   h.insertKey(2);
   h.insertKey(3);
   h.insertKey(1);
   h.insertKey(45);
   h.insertKey(5);
   h.insertKey(4);
   cout << "minimum element: " << h.extractMin() << endl;
   cout << "second minimum element: " << h.getMin() << endl;
   return 0;
}

Output

minimum element: 1
second minimum element: 2


You can also practice with the help of Online C++ Compiler

Min Heap C++ Representation

An array is used to store MinHeap. Arr[0] is the root element.

For a node at index i:

  • (i-1)/2 is the index of the parent node.
  • (2*i + 1) is the index of the left child.
  • (2*i + 2) is the index of the right child.
Representation of Min Heap

Important Methods of MinHeap

  • insert(): A new element is added at the end of the heap array. And then heap property is restored by swapping the current element with the parent until the value of the parent is greater than the current value. The time complexity of insertion in MinHeap is O(Logn).
     
  • getMin(): It returns the value of the root element (minimum element). The time complexity of getMin in MinHeap is O(1).
     
  • extractMin(): This method deletes and returns the root element of MinHeap. It swaps the root element with the last element of the heap array and then performs the Heapify operation on the MinHeap. Time complexity of extractMin() is O(Logn).
     
  • decreaseKey(): This method decreases the value of the key at index i. The time complexity of this method is O(Logn).
     
  • delete(): This method deletes the key at index i. The time complexity of deletion in MinHeap is O(Logn).

Another method for making min-heap using default priority_queue

Another method for creating a min heap in C++ using the default priority_queue involves using the negative of elements. This is based on the fact that priority_queue by default creates a max heap.

  • C++

C++

#include <iostream>
#include <queue>

int main() {
std::priority_queue<int> maxHeap;

// Inserting elements into max heap
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
maxHeap.push(1);
maxHeap.push(5);

// Displaying max heap elements
while (!maxHeap.empty()) {
std::cout << maxHeap.top() << " ";
maxHeap.pop();
}

return 0;
}

Output:

output

Explanation: In this example, the negative of the elements is inserted into the max heap, effectively creating a min heap when considering the negation. Keep in mind that this is a workaround and might not be as intuitive or clean as using greater in the comparator for min-heap creation.

Properties of Binary Heap

Properties of Binary Heap are as follows:

  • It is a complete tree. That is, all levels are completely filled. The last level might not be completely filled, but all its elements are all to the left side. Because of this property, the binary heap can be stored in a 1D array.
  • A binary heap can be either Min Heap or Max Heap. In Min/Max Heap the value of the root element is minimum/maximum.

Frequently Asked Questions

How min heap is implemented?

To construct a min heap, we add a new child node at the end of the heap (last level). Insert the new key into that node (append it to the array). Move the child node up until you reach the root node, at which point the heap property is satisfied.

Does C++ have a max heap?

Yes, C++ has a max heap. You can use heap via the standard template library of C++. Heap in STL is referred to as a priority queue. Each child node in a max heap data structure is less than or equal to its parent node.

Why do we use heap in C++?

Heap in C++ follows the hierarchical data structure. Internally, A heap is used when huge memory variables need to be utilized globally, and resizing is required regularly. Also, Memory is allocated in the application's heap section when using the new operator in C++. 

Is min heap a priority queue?

Yes, the min heap is a priority queue. In C++, both heaps are referred to as priority queues which can be accessed using C++ standard template library. The top element is always the greatest by default in the C++ STL.

How do you create a min heap in C++?

To create a min heap in C++, use the priority_queue container with the default comparator, which orders elements in descending order. For min heap, define it as priority_queue<int, vector<int>, greater<int>> minHeap;.

Conclusion

In this article, we learnt about the implementation of Min Heap in C++ using priority queue. We also looked at some of the most important methods of Min Heap. We have also discussed properties of Binary heap.

Also check this out: Turbo C++

We hope that this blog has helped you enhance your knowledge regarding Min Heap in C++ and if you would like to learn more, check out our articles on the platform Coding Ninjas Studio. Also, do check out our course on C++. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Std::stoull and std::stoul in Cpp
Next article
Design Twitter
Live masterclass