Insertion in Heaps

steps:

• increase the heap size by 1.
• Insert the new element at the end of the Heap.
• heapify this newly inserted element following a bottom-up approach.

Suppose the Heap is a Max-Heap as:

The new element to be inserted is 15.

steps:

Step 1: Insert the new element at the end.

Step 2: Heapify the new element following bottom-up 

        approach.

-> 15 is greater than its parent 4, swap them.

-> 15 is again greater than its parent 12 , swap them.

Therefore, the final heap after insertion is

and this follows the max heap properties.

implementation (for max heap):

arr[] is an array 

n is the size

i is the node to be heapified

key is  the inserted element.

in c++: 

void maxheapify(int arr[], int n, int i)
{
    // Find parent
    int parent = (i - 1) / 2;

    if (parent >= 0) {

        // For Max-Heap
        // If current node is greater than its parent
        // Swap both of them and call heapify again
        // for the parent
        if (arr[i] > arr[parent]) {
            swap(arr[i], arr[parent]);

            // Recursively heapify the parent node
            maxheapify(arr, n, parent);
        }
    }
}

// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
    // Increase the size of Heap by 1
    n = n + 1;

    // Insert the element at end of Heap
    arr[n - 1] = Key;

    // Heapify the new node following a
    // Bottom-up approach
    maxheapify(arr, n, n - 1);
}

java:

      private void maxheapify(int i)
    {   
        int n=size+1 ;

        // Find parent
    int parent = (i - 1) / 2;

    if (parent >= 0) {

        // For Max-Heap
        // If current node is greater than its parent
        // Swap both of them and call heapify again
        // for the parent
        if (arr[i] > arr[parent]) {
            int temp=arr[parent];
            arr[parent]=arr[i];
            arr[i]=temp;
            // swap
            // Recursively heapify the parent node
            maxheapify(parent);
        }
    }
    }

    // Function to insert key to heap
    // Inserts a new element to max heap 
    public void insert(int element) 
    { 
        arr[++size] = element; 
        if(size>0)
            heapify(size);
    } 
    

similar procedure for the min heap.