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++.

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; }

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.

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:

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.

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!