Shreyansh Jain's Blog

Heap Data Structures (Part - 2)

Shreyansh Jain's photo
Shreyansh Jain
·

4 min read

Heap Data Structures (Part - 2)

Table of contents

Pre-requisite

I would recommend going through part 1 of the heap data structures for a better understanding. You can read it here:- https://jainshreyansh.com/heap-data-structures-part-1

In this part, I am going to discuss how can we implement heap using C++.

Implementation

I am going to cover min-heap here. The max-heap is just the reverse. There are three main operations:-

  1. Creating min heap from the given array.

  2. Adding an element to a min-heap.

  3. Removing an element from the min heap.

The above operations will either use heapifyUp (or bubbling up) or heapifyDown (or bubbling down). Let's first implement these two.

Before this, let's create some helper function

void printMinHeap(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";    
    }
    cout << endl;
}

int getLeftChildIndex(int parentIndex) {
    return parentIndex * 2 + 1;
}

int getRightChildIndex(int parentIndex) {
    return parentIndex * 2 + 2;
}

int getParentIndex(int childIndex) {
    return  (childIndex - 1) / 2;
}

HeapifyUp

When we refer to "heapifyUp," we're describing the process of repositioning an element by comparing it to its parent node. If the element is smaller than its parent, we perform a swap to move it higher up the structure. This operation maintains the heap's integrity, ensuring that the parent nodes always contain smaller values than their child nodes in a min-heap or larger values in a max-heap.

void heapifyUp(vector<int> &arr, int index) {
    int parentIndex = getParentIndex(index);
    while (parentIndex >= 0 && arr[index] < arr[parentIndex]) {
        swap(arr[parentIndex], arr[index]);
        index = parentIndex;
        parentIndex = getParentIndex(index);
    }
}

HeapifyDown

In heapifyDown, we compare the parentIndex with the left and right child. If the value of parentIndex is less than both of left and right child, then min-heap's integrity is maintained and we don't need to do anything.

Otherwise, we need to swap it with whichever is the minimum right or left node.

void heapifyDown(vector<int> &arr, int parentIndex) {
    int leftChildIndex = getLeftChildIndex(parentIndex);  
    int smallerChildIndex;    
    while (leftChildIndex < arr.size()) {
        // we need to find out which is smaller
        // left child or right child.
        smallerChildIndex = leftChildIndex;
        int rightChildIndex = getRightChildIndex(parentIndex);
        if (rightChildIndex < arr.size() &&
            arr[rightChildIndex] < arr[smallerChildIndex]) {
            smallerChildIndex = rightChildIndex;        
        }
        if (arr[parentIndex] < arr[smallerChildIndex]) {
            // this condition implies, min-heap integrity is
            // already maintained.    
            break;
        }
        swap(arr[parentIndex], arr[smallerChildIndex]);
        parentIndex = smallerChildIndex;
        leftChildIndex = getLeftChildIndex(parentIndex);
    }
}

Creating a min-heap from an array.

To create a min-heap we will heapifyDown all the elements starting from the end.

The key thing to notice here is that we don't need to heapifyDown the leaf nodes since they don't have any child. So, instead of starting from n - 1 index, we can start from the first non-leaf node.

The first non-leaf node would be nothing but the parent of the last index, which is (n - 2 ) / 2 or n/2 - 1

void createMinHeap(vector<int> &arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapifyDown(arr, i);    
    }
}

Adding element to the min-heap

To add an element to the min-heap, we first add it as the last element in the array, but this may not be the correct position for it, so we need to heapify it up.

    void addElement(vector<int> &arr, int newEle) {
        arr.push_back(newEle);
        heapifyUp(arr, arr.size() - 1);
    }

Remove the minimum element from the min-heap

The minimum element is the first element of the array, so we swap it with the last element and pop it. Later we, heapifyDown the firstIndex so it reaches the correct position.

void removeElement(vector<int> &arr) {
     int n = arr.size();
     swap(arr[n - 1], arr[0]);
     arr.pop_back();
     heapifyDown(arr, 0);
}

Final step

Invoking all the functions.

You can check the running code at https://ideone.com/b2dYYF

int main() {
    vector<int> arr = {10, 22, 32, 6, 25, 22, 15, 56, 65, 72};
    createMinHeap(arr); 
    printMinHeap(arr);
    // 6 10 15 22 25 22 32 56 65 72
    addElement(arr, 8);
    printMinHeap(arr);
    // 6 8 15 22 10 22 32 56 65 72 25 
    removeElement(arr);
    printMinHeap(arr);
    // 8 10 15 22 25 22 32 56 65 72 
    removeElement(arr);
    printMinHeap(arr);
    // 10 22 15 56 25 22 32 72 65
}

Do upvote and follow me, if you like my post :)

heapDSA