How to Insert an element into Heap with C++ Code

What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

What is Heap?

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Any node of a heap must satisfy the heap property. For example in maxheap any parent node have a greater element then any element of child.

Types of Heap

There are two types of heap. They are:

1. Max Heap
2. Min Heap

Max Heap

Max heap is a complete binary tree where each node has a greater value then any of its children.

Min Heap

Min heap is a complete binary tree where each node have a smaller value than any of its children.

Difference Between Binary Search Tree & Heap

Binary Search Tree	Heap
A tree is said to be Binary Search Tree if all node have a greater vale than left node and smaller value than right node.	A tree is said to be Heap if all node have a greater value than its children (max heap) or smaller value than its children (min heap).
Binary Search Tree maybe complete or not.	Heap is always a complete tree.
Binary Search Tree is easy to search an element.	Heap is easy to insert or delete an element from the list.
Time complexity for Binary Search Tree is O(h). Where h is the height or depth of the tree.	Time complexity for Heap is O(log(n)). Where n is the number of nodes in the heap.

Insert into Heap

To insert an element into heap we need to follow 2 steps:

1. Insert the element at last position of the heap and increase the size of heap n to n+1.
2. Recursively test and swap the new value with previous/parent node as long as the heap property is not satisfied. For max heap swap if new value is greater than previous/parent node. For min heap swap if new value is smaller than previous/parent node.

C++ Code to Insert into Max Heap

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,i,m;          //n is no of elements,i is normal integer and m is used to not change n
    cout<<"How Much Elements are in Your Heap: ";
    cin>>n;

    long H[n+5];        //H is Array to take input the elements of heap
    cout<<"Enter All Elements of Heap in Sequential Representation:"<<endl;
    for(i=1;i<=n;i++){
        cin>>H[i];
    }
    cout<<endl;

    cout<<"Before Insertion:"<<endl;
    for(i=1;i<=n;i++){
        cout<<H[i]<<" ";
    }
    cout<<endl<<endl;

    cout<<"What will you Insert Now: ";
    cin>>H[n+1];                //Inserting new element at the last of heap tree
    cout<<endl;
    m=n=n+1;                    //Increasing total element number in heap

    while(H[m]>H[m/2]){         //Taking in exact position the inserted element
        swap(H[m],H[m/2]);
        m=m/2;
    }

    cout<<"After Insertion:"<<endl;
    for(i=1;i<=n;i++){
        cout<<H[i]<<" ";
    }
    cout<<endl;
    return 0;
}

C++ Code to Insert into Min Heap

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,i,m;          //n is no of elements,i is normal integer and m is used to not change n
    cout<<"How Much Elements are in Your Heap: ";
    cin>>n;

    long H[n+5];        //H is Array to take input the elements of heap
    cout<<"Enter All Elements of Heap in Sequential Representation:"<<endl;
    for(i=1;i<=n;i++){
        cin>>H[i];
    }
    cout<<endl;

    cout<<"Before Insertion:"<<endl;
    for(i=1;i<=n;i++){
        cout<<H[i]<<" ";
    }
    cout<<endl<<endl;

    cout<<"What will you Insert Now: ";
    cin>>H[n+1];                //Inserting new element at the last of heap tree
    cout<<endl;
    m=n=n+1;                    //Increasing total element number in heap

    while(H[m]<H[m/2]){         //Taking in exact position the inserted element
        swap(H[m],H[m/2]);
        m=m/2;
    }

    cout<<"After Insertion:"<<endl;
    for(i=1;i<=n;i++){
        cout<<H[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Hope your experience with this tutorial is quite good. Comment how do you feel about this tutorial. If you have any confusion you can also comment here. Subscribe for latest posts.