Implement min heap in C++

How to implement Min Heap?

To implement a Min Heap, we typically use an array-based representation, with the following operations:

Basic Structure

• Parent Node: For any node at index i, its left child is at index 2*i + 1, and its right child is at index 2*i + 2.
• Heap Property: The value of each parent node is less than or equal to the values of its children.

Operations

• Insertion: Add the new element at the end of the heap (maintaining complete binary tree property), then "heapify" (bubble-up) to restore the Min Heap property.
• Deletion (Extract-Min): Remove the root element, replace it with the last element, and "heapify" (bubble-down) to restore the Min Heap property.
• Heapify: Ensure that the tree follows the Min Heap property by recursively adjusting the positions of elements.

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

You can also try this code with Online C++ Compiler

Run Code

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.

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

You can also try this code with Online C++ Compiler

Run Code

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.