Implementation of Heap

Ishita Chawla
Last Updated: May 13, 2022

Introduction

A heap is a tree-based data structure where the element with the highest or the lowest priority is always stored at the ‘root’ of the tree.

A heap is a complete binary tree, in which all levels except the last, must be completely filled, and left-justified, which means the left subtree is filled before the right subtree. 

The complete binary tree is always balanced in order to guarantee logarithmic performance.

The most common misconception about heaps is that they are sorted. However, the truth is that they are actually ‘partially ordered’ and not at all sorted. Moreover, the children nodes at any particular level are not at all related to each other.

A binary heap is the most common type of heap used, with each node having at most 2 children. Since it is a complete binary tree, it has the shortest height, i.e., log N, where ‘N’ is the total number of nodes in the binary tree.

Types of Heap 

There are mainly two types of heaps:

Min Heap

In a min heap, the root node is the smallest of all the other nodes in the tree, and the value of every parent node is always smaller than or equal to the value of the child nodes.

Max Heap

In a max heap, the value of the root node is the largest of all the other nodes in the tree and the value of every parent node is always greater than or equal to the value of the child nodes.

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 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 Implementation

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

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

Key Takeaways

So, this blog discussed the concepts of a heap, differences between a min heap and a max heap, 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 CodeStudio to practice important heap problems and crack your interviews like a Ninja!

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

By Ishita Chawla

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think