Deletion in Heap

Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.

The standard deletion operation on Heap is to delete the element present at the root node of the Heap. That is if it is a Max Heap, the standard deletion operation will delete the maximum element and if it is a Min heap, it will delete the minimum element.

Process of Deletion:
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.

Replace the root or element to be deleted by 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 root.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4
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.
      4
    /    \
   5      3
  / 
 2   
Step 2: Heapify root.
Final Heap:
      5
    /    \
   4      3
  / 
 2

Implementation:

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);
    }
}

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.

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>

Output

5 4 3 2

Time complexity: O(logn) 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

Deletion in Heap

C++

Java

Python3

C#

Javascript

Insertion and Deletion in Heaps

Similar Reads

Contact Us