Binary Heap Implementation

Representation of Binary heaps

A binary heap is space-efficient and can be easily represented in an array. We should keep the following points in mind while representing a binary heap in an array.

In an array, ‘ARR’:

Consider the following example:

The above binary tree is a complete binary tree so we can represent it in an array in the following way:

Thus we start with level 0, i.e., element “10,” and fill it as the first element of the array and then increment the pointer. Now we are at level 1, and we will fill the array with the first child node at this level, i.e., with the number “9,” and then proceed to the number “8”.

Similarly, now we will start with the first element of level 2 and fill our array accordingly. 

A binary heap follows level order traversal, which means every node on a level is visited before going on to the next level. In this way, a binary heap can easily be stored in an array. 

Binary Heap Operations

A number of operations can be performed on a binary heap, some of which are listed below: (Please note that the operations discussed below are in terms of Max Heap)

1. maxHeapify():

MaxHeapify is the function responsible for restoring the property of the Max Heap. It arranges the node i, and its subtrees accordingly so that the heap property is maintained.

The following steps explain the function in detail:

1. Suppose we have given an array, ‘ARR’ representing the complete binary tree.
2. We set the index of the current element, ‘i’, as the ‘LARGEST’.
3. If ARR[2 * i + 1] > ARR[i], i.e., the left child is larger than the current value, it is set as ‘LARGEST’.
4. Similarly if ARR[2 * i + 2] > ARR[i], i.e., the right child is larger than the current value, it is set as ‘LARGEST’.
5. Swap the ‘LARGEST’ with the current element.
6. Repeat steps 1-4 till the property of the heap is restored.

Let us dry run the above steps using an example:

2. insertKey():

While insertion, the new element is appended at the end of the heap and becomes the last element of the array. If the newly added element is smaller than the parent, nothing has to be done. Otherwise, the values are swapped until the property of the heap is restored.

3. increaseKey():

Increases the value of a key at a particular index to some value. If this new value is smaller than the parent node, nothing has to be done. Otherwise, the property of the heap is violated and swaps are made to restore it.

4. getMax():

Returns the maximum element stored at the root node of the Max heap.

5. removeMax():

Removes the maximum element of the heap stored at the root and calls maxHeapify() to restore the property of the Max heap.

6. deletekey():

The element that has to be deleted is first replaced with positive infinity by calling increaseKey() and then we call removeMax() to remove this element from the heap.

The above operations are depicted in the code given below.

Code in C++

The following code shows the implementation of a Max Heap:

// C++ program to depict the implementation of a heap.
#include <bits/stdc++.h>
using namespace std;

// A class for Max Heap.
class MaxHeap
{
    // A pointer pointing to the elements in the array in the heap.
    int *arr;

    // Maximum possible size of the Max Heap.
    int maxSize;

    // Number of elements in the Max heap currently.
    int heapSize;

public:
    // Constructor function.
    MaxHeap(int maxSize);

    // Heapifies a sub-tree taking the given index as the root.
    void MaxHeapify(int);

    // Returns the index of the parent of the element at ith index.
    int parent(int i)
    {
        return (i - 1) / 2;
    }

    //Returns the index of the left child.
    int lChild(int i)
    {
        return (2 * i + 1);
    }

    // Returns the index of the right child.
    int rChild(int i)
    {
        return (2 * i + 2);
    }

    // Removes the root which in this case contains the maximum element.
    int removeMax();

    // Increases the value of the key given by index i to some new value.
    void increaseKey(int i, int newVal);

    // Returns the maximum key (key at root) from max heap.
    int getMax()
    {
        return arr[0];
    }

    int curSize()
    {
        return heapSize;
    }
    // Deletes a key at given index i.
    void deleteKey(int i);

    // Inserts a new key 'x' in the Max Heap.
    void insertKey(int x);
};

// Constructor function builds a heap from a given array a[] of the specified size.
MaxHeap::MaxHeap(int totSize)
{
    heapSize = 0;
    maxSize = totSize;
    arr = new int[totSize];
}

// Inserting a new key 'x'.
void MaxHeap::insertKey(int x)
{
    // To check whether the key can be inserted or not.
    if (heapSize == maxSize)
    {
        cout << "\nOverflow: Could not insertKey\n";
        return;
    }

    // The new key is initially inserted at the end.
    heapSize++;
    int i = heapSize - 1;
    arr[i] = x;

    // The max heap property is checked and if violation occurs, it is restored.
    while (i != 0 && arr[parent(i)] < arr[i])
    {
        swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

// Increases value of key at index 'i' to new_val. 
void MaxHeap::increaseKey(int i, int newVal)
{
    arr[i] = newVal;
    while (i != 0 && arr[parent(i)] < arr[i])
    {
        swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

// To remove the root node which contains the maximum element of the Max Heap.
int MaxHeap::removeMax()
{
    // Checking whether the heap array is empty or not.
    if (heapSize <= 0)
        return INT_MIN;
    if (heapSize == 1)
    {
        heapSize--;
        return arr[0];
    }

    // Storing the maximum element to remove it.
    int root = arr[0];
    arr[0] = arr[heapSize - 1];
    heapSize--;

    // To restore the property of the Max heap.
    MaxHeapify(0);

    return root;
}

// In order to delete a key at a given index i.
void MaxHeap::deleteKey(int i)
{
    // It increases the value of the key to infinity and then removes the maximum value.
    increaseKey(i, INT_MAX);
    removeMax();
}

// To heapify the subtree this method is called recursively
void MaxHeap::MaxHeapify(int i)
{
    int l = lChild(i);
    int r = rChild(i);
    int largest = i;
    if (l < heapSize && arr[l] > arr[i])
        largest = l;
    if (r < heapSize && arr[r] > arr[largest])
        largest = r;
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        MaxHeapify(largest);
    }
}

// Driver program to test above functions.
int main()
{
    // Assuming the maximum size of the heap to be 15.
    MaxHeap h(15);

    // Asking the user to input the keys:
    int k, i, n = 7, arr[10];
    cout << "Enter 7 keys of your choice: \n";
    for (i = 0; i < n; i++)
    {
        cin >> arr[i];
        h.insertKey(arr[i]);
    }

    // Printing the current size of the heap.
    cout << "The current size of the heap is " << h.curSize() << "\n";

    // Printing the root element which is actually the maximum element.
    cout << "The current maximum element is " << h.getMax() << "\n";

    // Deleting key at index 2.
    h.deleteKey(2);

    // Printing the size of the heap after deletion. 
    cout << "The current size of the heap is " << h.curSize() << "\n";

    // Inserting 2 new keys into the heap.
    h.insertKey(15);
    h.insertKey(5);
    cout << "The current size of the heap is " << h.curSize() << "\n";
    cout << "The current maximum element is " << h.getMax() << "\n";

    return 0;
}

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

Run Code

Input:

Enter 7 keys of your choice:
3
10
12
8
4
2
14 

Output:

The current size of the heap is 7       
The current maximum element is 14       
The current size of the heap is 6       
The current size of the heap is 8       
The current maximum element is 15  

Time Complexity:

The various time complexities of binary heap functions are discussed below:

1. Building Heap:
   Building a  heap generally takes O(N) time. It can be proved using the convergence of series.
2. Insertion:
   Inserting a new key to the heap requires the heapify() procedure which takes O(log (N)) time to restore the order of the tree as the height of the tree is O(log (N)). Thus the time complexity for insertion of a new key is O(log (N)).
3. Deletion:
   After the deletion of the root node or the key value, the tree is heapified in order to restore the property of the tree. Hence its complexity is also given by O(log N).
4. Getting the Minimum/ Maximum element:
   The minimum or maximum element is stored in the root node. Hence it can be accessed in simply 1 operation and hence its time complexity is O(1).
5. Extracting the Minimum/ Maximum element:
   Since this operation needs to call heapify() after removing the root element to restore the property of the heap, the time complexity is given by O(log (N)).

Applications

Some of the most important applications of the binary heap are:

1. Used in operating systems for scheduling jobs on a priority basis.
2. Used in graph algorithms like Dijkstra’s Algorithm (to find the shortest path), Minimum Spanning Tree, and Prim's Algorithm.
3. Used to perform heap sort.
4. Used to implement priority queues

Other Uses of Binary Heaps

Because heaps are relatively flexible Data Structures, memory allocation is usually very quick. In comparison to other data structures, element insertion and deletion are also quite fast.

The smallest and largest element can also be found very quickly as it is generally stored at the root node.

Data structures like linked lists and arrays require O(N) time to access the minimum or maximum element. However, a binary heap can access the minimum or maximum element in just O(1) time as the maximum or minimum element always lies at the root node and we simply have to return the element at the 0th index of the array.

You can also read about the - hash function in data structure

Frequently Asked Questions

What is the time complexity of insertion in Priority Queue?

The time complexity of insertion Priority Queue is log(N) where N is the size of the queue.

What is the Difference between Min-Priority Queue and Max-Priority Queue?

The Min-Priority Queue has the Minimum Element at the Top whereas the Max-Priority Queue has the Maximum Element at the Top

Conclusion

So, this blog discussed the concepts of a heap, differences between a min heap and a max heap, the implementation of a heap, and various operations that can be performed on a  binary heap. 

The blog also tried to provide a better understanding of the time complexities of various operations, as well as the advantages, disadvantages, and applications of heaps in various fields. 

To learn more, head over right now to Coding Ninjas Studio to practice important heap problems and crack your interviews like a Ninja!

Recommended Readings:

• Min Heap
• Linked Lists
• Applications of Heap
• Binary Heap
• Tournament Trees and Binary Heaps
• Heap and Priority Queue
• Application of Priority Queue
• Application of Linked List

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

In case of any comments or suggestions, feel free to post them in the comments section.