Insertion in Heaps

The insertion operation is also similar to that of the deletion process.

Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element to the Heap maintaining the properties of Heap.

Process of Insertion: Elements can be inserted to the heap following a similar approach as discussed above for deletion. The idea is to:

First increase the heap size by 1, so that it can store the new element.
Insert the new element at the end of the Heap.
This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4
The new element to be inserted is 15.
Process:
Step 1: Insert the new element at the end.
      10
    /    \
   5      3
  / \    /
 2   4  15
Step 2: Heapify the new element following bottom-up 
        approach.
-> 15 is more than its parent 3, swap them.
       10
    /    \
   5      15
  / \    /
 2   4  3
-> 15 is again more than its parent 10, swap them.
       15
    /    \
   5      10
  / \    /
 2   4  3
Therefore, the final heap after insertion is:
       15
    /    \
   5      10
  / \    /
 2   4  3

Implementation:

C++

// C++ program to insert new element to Heap
 
#include <iostream>
using namespace std;
 
#define MAX 1000 // Max size of Heap
 
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
void heapify(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 
            heapify(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
    heapify(arr, n, n - 1);
}
 
// A utility function to print array of size n
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
 
    cout << "\n";
}
 
// Driver Code
int main()
{
    // Array representation of Max-Heap
    // 10
    //    /  \
    // 5    3
    //  / \
    // 2   4
    int arr[MAX] = { 10, 5, 3, 2, 4 };
 
    int n = 5;
 
    int key = 15;
 
    insertNode(arr, n, key);
 
    printArray(arr, n);
    // Final Heap will be:
    // 15
    //    /   \
    // 5     10
    //  / \   /
    // 2   4 3
    return 0;
}

Java

// Java program for implementing insertion in Heaps
public class insertionHeap {
 
    // Function to heapify ith node in a Heap
    // of size n following a Bottom-up approach
    static void heapify(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] and arr[parent]
                int temp = arr[i];
                arr[i] = arr[parent];
                arr[parent] = temp;
               
                // Recursively heapify the parent node
                heapify(arr, n, parent);
            }
        }
    }
 
    // Function to insert a new node to the heap. 
    static int 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
        heapify(arr, n, n - 1);
         
        // return new size of Heap
        return n;
    }
 
    /* A utility function to print array of size n */
    static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; ++i)
            System.out.println(arr[i] + " ");
 
        System.out.println();
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Array representation of Max-Heap
        // 10
        //    /  \
        // 5    3
        //  / \
        // 2   4
         
        // maximum size of the array
        int MAX = 1000;
        int[] arr = new int[MAX];
         
        // initializing some values 
        arr[0] = 10;
        arr[1] = 5;
        arr[2] = 3;
        arr[3] = 2;
        arr[4] = 4;
         
        // Current size of the array 
        int n = 5;
 
        // the element to be inserted 
        int Key = 15;
         
        // The function inserts the new element to the heap and 
        // returns the new size of the array
        n = insertNode(arr, n, Key);
 
        printArray(arr, n);
        // Final Heap will be:
        // 15
        //    /   \
        // 5     10
        //  / \   /
        // 2   4 3
    }
}
 
// The code is contributed by Gautam goel

Python3

# program to insert new element to Heap
 
# Function to heapify ith node in a Heap
# of size n following a Bottom-up approach
 
 
def heapify(arr, n, i):
    parent = int(((i-1)/2))
    # For Max-Heap
    # If current node is greater than its parent
    # Swap both of them and call heapify again
    # for the parent
    if parent >= 0:
        if arr[i] > arr[parent]:
            arr[i], arr[parent] = arr[parent], arr[i]
            # Recursively heapify the parent node
            heapify(arr, n, parent)
# Function to insert a new node to the Heap
 
 
def insertNode(arr, key):
    global n
    # Increase the size of Heap by 1
    n += 1
    # Insert the element at end of Heap
    arr.append(key)
    # Heapify the new node following a
    # Bottom-up approach
    heapify(arr, n, n-1)
# A utility function to print array of size n
 
 
def printArr(arr, n):
    for i in range(n):
        print(arr[i], end=" ")
 
 
# Driver Code
# Array representation of Max-Heap
'''
        10
       /  \
      5    3
     / \
    2   4
'''
arr = [10, 5, 3, 2, 4, 1, 7]
n = 7
key = 15
insertNode(arr, key)
printArr(arr, n)
# Final Heap will be:
'''
      15
    /   \
   5     10
 /  \    /
2    4   3
 
Code is written by Rajat Kumar....
'''

C#

// C# program for implementing insertion in Heaps
 
using System;
 
public class insertionHeap {
 
    // Function to heapify ith node in a Heap of size n following a Bottom-up approach
    static void heapify(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] and arr[parent]
                int temp = arr[i];
                arr[i] = arr[parent];
                arr[parent] = temp;
 
                // Recursively heapify the parent node
                heapify(arr, n, parent);
            }
        }
    }
 
    // Function to insert a new node to the heap.
    static int 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
        heapify(arr, n, n - 1);
 
        // return new size of Heap
        return n;
    }
 
    /* A utility function to print array of size n */
    static void printArray(int[] arr, int n) {
        for (int i = 0; i < n; ++i)
            Console.WriteLine(arr[i] + " ");
 
        Console.WriteLine("");
    }
 
    public static void Main(string[] args) {
        // Array representation of Max-Heap
        //     10
        //    /  \
        //   5    3
        //  / \
        // 2   4
 
        // maximum size of the array
        int MAX = 1000;
        int[] arr = new int[MAX];
 
        // initializing some values
        arr[0] = 10;
        arr[1] = 5;
        arr[2] = 3;
        arr[3] = 2;
        arr[4] = 4;
 
        // Current size of the array
        int n = 5;
 
        // the element to be inserted
        int Key = 15;
 
        // The function inserts the new element to the heap and
        // returns the new size of the array
        n = insertNode(arr, n, Key);
 
        printArray(arr, n);
        // Final Heap will be:
        //      15
        //    /   \
        //   5     10
        //  / \   /
        // 2   4 3
    }
}
 
// This code is contributed by ajaymakvana.

Javascript

// Javascript program for implement insertion in Heaps 
 
// To heapify a subtree rooted with node i which is 
// an index in arr[].Nn is size of heap 
 
let MAX = 1000; 
 
// Function to heapify ith node in a Heap of size n following a Bottom-up approach
function heapify(arr, n, i)
{
    // Find parent
    let parent = Math.floor((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]) {
            let temp = arr[i];
            arr[i] = arr[parent];
            arr[parent] = temp;
 
            // Recursively heapify the parent node
            heapify(arr, n, parent);
        }
    }
}
 
// Function to insert a new node to the Heap
function insertNode(arr, n, 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
    heapify(arr, n, n - 1);
     
    return n;
}
 
/* A utility function to print array of size N */
function printArray(arr, n) 
{ 
    for (let i = 0; i < n; ++i) 
        console.log(arr[i] + " "); 
 
    console.log("</br>"); 
}
 
let arr = [ 10, 5, 3, 2, 4 ];
 
let n = arr.length;
 
let key = 15;
 
n = insertNode(arr, n, key);
 
printArray(arr, n);
 
// This code is contributed by ajaymakvana

Output

15 5 10 2 4 3

Time Complexity: O(log(n)) (where n is no of elements in the heap)
Auxiliary Space: O(n)

C++

Java

Python3

C#

Javascript

Insertion and Deletion in Heaps

Contact Us

Insertion in Heaps

C++

Java

Python3

C#

Javascript

Insertion and Deletion in Heaps

Similar Reads

Contact Us