Deletion in Max-Heap Data Structure

1. Insertion in Max-Heap Data Structure:

3. Peek operation on Max-heap Data Structure:

Deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted with the last element and delete the last element of the Heap.

Replace the root or element to be deleted with the last element.
Delete the last element from the Heap.
Since the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of the root.

Illustration:

Suppose the Heap is a Max-Heap as:

Max Heap Data Structure

The element to be deleted is root, i.e. 10.

Process:

The last element is 4.

Step 1: Replace the last element with root, and delete it.

Max Heap

Step 2: Heapify root.

Final Heap:

Max Heap

Implementation of Deletion operation in Max-Heap:

C++

// C++ program for implement deletion in Heaps
 
#include <iostream>
 
using namespace std;
 
// To heapify a subtree rooted with node i which is
// an index of arr[] and n is the size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2
 
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
 
// Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];
 
    // Replace root with last element
    arr[0] = lastElement;
 
    // Decrease size of heap by 1
    n = n - 1;
 
    // heapify the root node
    heapify(arr, n, 0);
}
 
/* 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[] = { 10, 5, 3, 2, 4 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    deleteRoot(arr, n);
 
    printArray(arr, n);
 
    return 0;
}

Java

// Java program for implement deletion in Heaps
public class deletionHeap {
 
    // To heapify a subtree rooted with node i which is
    // an index in arr[].Nn is size of heap
    static void heapify(int arr[], int n, int i)
    {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
 
    // Function to delete the root from Heap
    static int deleteRoot(int arr[], int n)
    {
        // Get the last element
        int lastElement = arr[n - 1];
 
        // Replace root with first element
        arr[0] = lastElement;
 
        // Decrease size of heap by 1
        n = n - 1;
 
        // heapify the root node
        heapify(arr, n, 0);
 
        // 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.print(arr[i] + " ");
 
        System.out.println();
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Array representation of Max-Heap
        // 10
        // / \
        // 5 3
        // / \
        // 2 4
        int arr[] = { 10, 5, 3, 2, 4 };
 
        int n = arr.length;
 
        n = deleteRoot(arr, n);
 
        printArray(arr, n);
    }
}

C#

// C# program for implement deletion in Heaps
using System;
 
public class deletionHeap
{
 
    // To heapify a subtree rooted with node i which is
    // an index in arr[].Nn is size of heap
    static void heapify(int []arr, int n, int i)
    {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
 
    // Function to delete the root from Heap
    static int deleteRoot(int []arr, int n)
    {
        // Get the last element
        int lastElement = arr[n - 1];
 
        // Replace root with first element
        arr[0] = lastElement;
 
        // Decrease size of heap by 1
        n = n - 1;
 
        // heapify the root node
        heapify(arr, n, 0);
 
        // 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.Write(arr[i] + " ");
 
        Console.WriteLine();
    }
 
    // Driver Code
    public static void Main()
    {
        // Array representation of Max-Heap
        // 10
        // / \
        // 5 3
        // / \
        // 2 4
        int []arr = { 10, 5, 3, 2, 4 };
        int n = arr.Length;
        n = deleteRoot(arr, n);
        printArray(arr, n);
    }
}
 
// This code is contributed by Ryuga

Javascript

<script>
    // Javascript program for implement deletion in Heaps
     
    // To heapify a subtree rooted with node i which is
    // an index in arr[].Nn is size of heap
    function heapify(arr, n, i)
    {
        let largest = i; // Initialize largest as root
        let l = 2 * i + 1; // left = 2*i + 1
        let r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i)
        {
            let swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
 
    // Function to delete the root from Heap
    function deleteRoot(arr, n)
    {
        // Get the last element
        let lastElement = arr[n - 1];
 
        // Replace root with first element
        arr[0] = lastElement;
 
        // Decrease size of heap by 1
        n = n - 1;
 
        // heapify the root node
        heapify(arr, n, 0);
 
        // return new size of Heap
        return n;
    }
 
    /* A utility function to print array of size N */
    function printArray(arr, n)
    {
        for (let i = 0; i < n; ++i)
            document.write(arr[i] + " ");
 
        document.write("</br>");
    }
     
    let arr = [ 10, 5, 3, 2, 4 ];
    let n = arr.length;
    n = deleteRoot(arr, n);
    printArray(arr, n);
 
// This code is contributed by divyeshrabdiya07.
</script>

Python3

# Python 3 program for implement deletion in Heaps
 
# To heapify a subtree rooted with node i which is
# an index of arr[] and n is the size of heap
def heapify(arr, n, i):
 
    largest = i #Initialize largest as root
    l = 2 * i + 1 # left = 2*i + 1
    r = 2 * i + 2 # right = 2*i + 2
 
    #If left child is larger than root
    if (l < n and arr[l] > arr[largest]):
        largest = l
 
    #If right child is larger than largest so far
    if (r < n and arr[r] > arr[largest]):
        largest = r
 
    # If largest is not root
    if (largest != i):
        arr[i],arr[largest]=arr[largest],arr[i]
 
        #Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
 
#Function to delete the root from Heap
def deleteRoot(arr):
    global n
 
    # Get the last element
    lastElement = arr[n - 1]
 
    # Replace root with last element
    arr[0] = lastElement
 
    # Decrease size of heap by 1
    n = n - 1
 
    # heapify the root node
    heapify(arr, n, 0)
 
# A utility function to print array of size n
def printArray(arr, n):
 
    for i in range(n):
        print(arr[i],end=" ")
    print()
 
# Driver Code
if __name__ == '__main__':
 
    # Array representation of Max-Heap
    #     10
    #     / \
    # 5 3
    # / \
    # 2 4
    arr = [ 10, 5, 3, 2, 4 ]
 
    n = len(arr)
 
    deleteRoot(arr)
 
    printArray(arr, n)
     
    # This code is contributed by Rajat Kumar.

Output

5 4 3 2

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.