Binary Heap

Introduction

This blog discusses the concept and implementation of one of the most popular and important data structures in computer science - Binary Heap. Binary Heap is a widely asked data structure in coding contests and technical interviews. We can use binary heaps to organize our data in such a way that operations like insert, delete, decrease an element, delete min/max element can be implemented in log(N) time, where N is the total number of elements in the data. There are several interesting applications of binary heaps, which we will discuss in this blog.

Problem Statement

Ninja has given you the task to implement a data structure that possesses the following characteristics:

Structure-wise, it should be a complete binary tree, i.e., all levels in the tree should be completely filled except possibly the last level. Also, in the last level, all nodes should be as left as possible.
Binary Heap is either a min-heap or max-heap. Your task is to create a min-heap that satisfies the following property:
1. The key at each node N should be minimum among all keys in the subtree of the node N.

As you can guess, in the case of a max-heap, the key at each node N is the maximum among all keys in the subtree of the node N.

The data structure containing N elements should support the following operations:

insert function: Inserts the given element into the data structure in O(logN) time.
deleteKey function: Deletes the given element in the data in O(logN) time.
getMin function: Returns the minimum element in the data in O(1) time.
extractMin function: Deletes the minimum element in the data in O(logN) time.
decreaseKey function: Decrease the value of an element in O(logN) time.

Input

Data: {10, 30, 20, 100}

Output

/ \

20 100

Input

Data: {10, 15, 40, 50, 30, 40, 100}

Output

/ \

15 30

/ \ / \

40 50 100 40

Approach

The first and foremost question that comes to our mind - How should we represent the data structure - Using pointers or in an array?

Well, as binary heaps are complete binary trees, we can represent them using an array. Let BINARY_HEAP be the array used for representation.

The root element is placed at binaryHeap[0].
For ith node:
1. BINARY_HEAP[(i - 1) / 2] returns the index of the parent node (i != 0).
2. BINARY_HEAP[2 * i + 1] returns the index of the left child if it exists.
3. BINARY_HEAP[2 * i + 2] returns the index of the right child if it exists.

Example:

We will be using two primary functions to implement the heap data structure:

heapify() function: Given a node, compare the node's value with its children. If the node's value is greater than any one of its children, swap the node with its children of minimum key value. Recursively call the heapify function for the new position of the node.
restoreProperty() function: Given a node, check if its parent has a greater key than the node itself. Suppose this is true, swap the node with its parent and call the restoreProperty() function recursively for the new position of the node.

We can implement insert, deleteKey, etc., operations using the functions described above as explained in the algorithm below.

Algorithm

Create a class BHeap and declare the following parameters:
1. ‘CAPACITY’: To indicate the maximum number of elements in the binary heap.
2. ‘HEAPSIZE’: To indicate the current number of elements in the binary heap.
3. ‘BINARYHEAP’: The array to hold the binary heap tree.
Create parent(), leftChild(), and rightChild() functions as described in the approach above.
Implementation of restoreProperty() function
1. It takes the index of a heap node as a parameter.
2. Let ‘P’ be the parent of the node ‘IND’. If the parent node's value is greater than the current node, swap the node with its parent.
3. If the above condition is true, call the restoreProperty() function with the index of the parent node.
Implementation of heapify function
1. It takes the index of a heap node as a parameter.
2. Let ‘RIGHT’ and ‘LEFT’ be the indices of its right and left children.
3. Let i be the index of the minimum-key node among these three nodes.
4. If i is not equal to the node's index passed as a parameter, swap with the node at index i and recursively call the heapify() function with i passed as a parameter.
We can implement the binary heap functions with the help of these functions as implemented in the code below.

Program

#include <iostream>
#include <climits>
using namespace std;

// Binary Heap Class.
class BHeap
{
    int *binaryHeap;
    int heapSize;
    int capacity;

public:
    // Constructor to create an object.
    BHeap(int capacity);

    // Function to insert an element into the heap.
    void insert(int key);

    // Function to remove an element from the heap.
    void deleteKey(int index);

    // Remove the min-key node from the heap.
    void extractMin();

    // Decrease the key value of a node.
    void decreaseKey(int index, int newKey);

    // Get the minimum key from the data.
    int getMin();

    // To get the parent of a non-root node.
    int parent(int index);

    // To get the left child of a node.
    int leftChild(int index);

    // To get the right child of a node.
    int rightChild(int index);

    // Function to restore the property of binary heaps.
    void restoreProperty(int index);

    // Function to push a node down the binary heap.
    void heapify(int index);
};

// Constructor implementation.
BHeap::BHeap(int capacity)
{
    // Initialize the object parameters.
    capacity = capacity;
    heapSize = 0;
    binaryHeap = new int[capacity];
}

// Function to push a node up the tree to maintain binary heap property.
void BHeap::restoreProperty(int index)
{
    // If it is the root, return as we cannot go up any further.
    if (index == 0)
        return;

    // If the node's key is less than its parent, swap and call the recursive function for its parent.
    if (binaryHeap[parent(index)] > binaryHeap[index])
    {
        swap(binaryHeap[index], binaryHeap[parent(index)]);
        heapify(parent(index));
    }
}

// Function to push a node down the tree to maintain binary heap property.
void BHeap::heapify(int index)
{
    // Find the left and children.
    int left = leftChild(index);
    int right = rightChild(index);

    // Currently, the smallest node is the node itself.
    int smallest = index;

    // Check for the left and right children if they are smaller than their parents.
    if (left < heapSize && binaryHeap[left] < binaryHeap[index])
        smallest = left;
    if (right < heapSize && binaryHeap[right] < binaryHeap[smallest])
        smallest = right;

    // If it is the case stated above, swap and recursively call for the pushed down node.
    if (smallest != index)
    {
        swap(binaryHeap[index], binaryHeap[smallest]);
        heapify(smallest);
    }
}

// Function to find the parent of a node.
int BHeap::parent(int index)
{
    return (index - 1) / 2;
}

// Function to find the left child of a node.
int BHeap::leftChild(int index)
{
    return 2 * index + 1;
}

// Function to find the right child of a node.
int BHeap::rightChild(int index)
{
    return 2 * index + 2;
}

// Function to get the minimum node in the binary heap.
int BHeap::getMin()
{
    // If the heap is empty, return INT_MAX;
    if (heapSize == 0)
    {
        printf("Underflow\n");
        return INT_MAX;
    }
    return binaryHeap[0];
}

// Function to remove the minimum-key node, i.e., the topmost node.
void BHeap::extractMin()
{
    if (heapSize == 0)
    {
        printf("Underflow\n");
    }

    // First swap with the bottomost rightmost node and decrease the heap size to abandon the last node.
    swap(binaryHeap[0], binaryHeap[heapSize - 1]);
    heapSize--;

    // Heapify the binary heap as the swap operation might change the property.
    heapify(0);
}

// Function to decrease a node's key.
void BHeap::decreaseKey(int index, int newkey)
{
    // Simply make the change and call restoreProperty() function as the key is to decrease only.
    binaryHeap[index] = newkey;
    restoreProperty(index);
}

// Function to delete a key using functions defined above.
void BHeap::deleteKey(int index)
{
    // Decrease the node's value to push it to the top and remove the minimum-key element.
    decreaseKey(index, INT_MIN);
    extractMin();
}

// Function to insert a key into the binary heap.
void BHeap::insert(int key)
{
    // Check if the heap is full already.
    if (heapSize == capacity)
    {
        printf("Overflow\n");
        return;
    }
    // Insert it and push it up if needed.
    binaryHeap[heapSize] = key;
    heapSize++;
    restoreProperty(heapSize - 1);
}

// Function to check the driver code.
int main()
{
    // Create a heap of size 11.
    BHeap binaryheap(11);

    // Insert the keys.
    binaryheap.insert(3);
    binaryheap.insert(2);
    binaryheap.deleteKey(1);
    binaryheap.insert(15);
    binaryheap.insert(5);
    binaryheap.insert(4);
    binaryheap.insert(45);

    // Get the minimum key in the binary heap.
    cout << binaryheap.getMin() << " ";

    // Decrease the key of node at index 2 to 1 making it the lowest.
    binaryheap.decreaseKey(2, 1);
    cout << binaryheap.getMin() << " ";

    // A bunch of extractMin and getMin function calls.
    binaryheap.extractMin();
    cout << binaryheap.getMin() << " ";
    binaryheap.extractMin();
    cout << binaryheap.getMin() << endl;

    return 0;
}

Input

Specified in the code.

Output

2 1 2 4

Applications

Binary Heaps are used in a variety of ways.

Heap Sort: Heap Sort sorts an array in O(Nlog N) time using Binary Heap.
Priority Queue: Because Binary Heap provides insert(), delete(), and extractmax(), decreaseKey() operations in O(log N) time, priority queues can be efficiently created. Binary Heap has two variants: Binomial Heap and Fibonacci Heap. These variants implement the union operation efficiently.
Priority queues are particularly useful in graph algorithms like Dijkstra's Shortest Path and Prim's Minimum Spanning Tree.

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

In this blog, we developed an in-depth understanding of the binary heap data structure. We can similarly create a max-heap data structure by tweaking the comparison signs in a few places. We saw various applications of binary heaps.

Recommended Readings: