Insertion in Max-Heap Data Structure

Operations on Max-heap Data Structure and their Implementation:

2. Deletion in Max-Heap Data Structure:

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:

Insertion in Max heap

Implementation of insertion operation in Max-Heap:

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 (arr[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 (arr[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

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 (arr[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 (arr[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

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 arr[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....
'''

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)

Introduction to Max-Heap – Data Structure and Algorithm Tutorials

A Max-Heap is defined as a type of Heap Data Structure in which each internal node is greater than or equal to its children.

The heap data structure is a type of binary tree that is commonly used in computer science for various purposes, including sorting, searching, and organizing data.

Introduction to Max-Heap Data Structure

Purpose and Use Cases of Max-Heap:

Priority Queue: One of the primary uses of the heap data structure is for implementing priority queues.

Heap Sort: The heap data structure is also used in sorting algorithms.

Memory Management: The heap data structure is also used in memory management. When a program needs to allocate memory dynamically, it uses the heap data structure to keep track of the available memory.

Graph Algorithms: The heap data structure is used in various graph algorithms. For example, Dijkstra’s shortest path algorithm uses a heap data structure to keep track of the vertices with the shortest path from the source vertex.