C++ program for Array Representation Of Binary Heap

In this tutorial, we are going to learn how to represent a Binary Heap using an array in C++. In a Binary Tree, if all the levels are completely filled excluding the last level and all the nodes in the last level are towards the left of the tree, then it is called a Binary Heap.

Example:

Properties:

Let A be an array which is used to represent a Binary Heap.

  1. A[0] is the root node.
  2. The left child of node A[i] is A[2*i + 1].
  3. The right child of node A[i] is A[2*i + 2].
  4. The parent of node A[i] is A[(i-1)/2 ].

There are two types of Binary Heaps:

  1. Min Heap: In a Min Heap the roots of all subtrees will have the minimum value among all the nodes present in their respective subtree.
  2. Max Heap: In a Max Heap the roots of all subtrees will have the maximum value among all the nodes present in their respective subtree.

C++ code for Array representation of a binary heap

#include<bits/stdc++.h>
using namespace std;
void Insert(int a[],int &size,int n,int key){
    //Inserts the new node at last
    if(size < n){
        a[size] = key;
        size++;
    }
    else{
        cout<<"Not enough space"<<endl;
    }

}
void Delete(int a[],int &size,int key){
    /*Finds the key and replaces it with
      last node and deletes the last node*/
    for(int i = 0;i < size;i++){
        if(a[i] == key){
            a[i] = a[size-1];
            size--;
            return;
        }
    }
    cout<<"Key not found"<<endl;
}
int getParent(int a[],int index){
    return (index - 1)/2;
}
int getLeftChild(int a[],int index){
    return 2*index +1;
}
int getRightChild(int a[],int index){
    return 2*index +2;
}
void printHeap(int a[],int size){
    for(int i = 0;i < size;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
}
int main(){
    //n is the max size of the heap
    int n = 100;
    int Heap[n];
    //size of the heap
    int size = 0;
    Insert(Heap,size,n,5);
    Insert(Heap,size,n,6);
    Insert(Heap,size,n,3);
    Insert(Heap,size,n,8);
    Insert(Heap,size,n,2);
    Insert(Heap,size,n,7);
    cout<<"Heap after insertions"<<endl;
    printHeap(Heap,size);
    Delete(Heap,size,3);
    cout<<"Heap after deleting the key 3"<<endl;
    printHeap(Heap,size);
    // Get parent of node at index 2
    int i = getParent(Heap,2);
    cout<<"Parent of the node at index 2 is "<<Heap[i]<<endl;
    // Get the left child of the node at index 1
    i = getLeftChild(Heap,1);
    if(i < size){
        cout<<"Left child of node at index 1 is "<<Heap[i]<<endl;
    }
    else{
        cout<<"Left child doesnot exist"<<endl;
    }
    i = getRightChild(Heap,1);
    if(i < size){
        cout<<"Right child of node at index 1 is "<<Heap[i]<<endl;
    }
    else{
        cout<<"Right child doesnot exist"<<endl;
    }

}

Output:

Heap after insertions
5 6 3 8 2 7 
Heap after deleting the key 3
5 6 7 8 2 
Parent of the node at index 2 is 5
Left child of node at index 1 is 8
Right child of node at index 1 is 2

 

Insert() function inserts the given key at the end of the heap.
Delete() function finds the position of the given key. It replaces the key with the value of the last node and deletes the last node.
getParent() function returns the parent’s index of a given index.
getLeftChild() function returns the left child’s index of a given index.
getRightChild() function returns the right child’s index of a given index.

 

We hope that you have got a clear idea of an array-based representation of a Binary Heap in C++.

Leave a Reply

Your email address will not be published. Required fields are marked *