Deletion in Min-Heap Data Structure

1. Insertion in Min-Heap Data Structure:

3. Peek operation on Min-Heap Data Structure:

Removing the smallest element (the root) from the min heap. The root is replaced by the last element in the heap, and then the heap property is restored by swapping the new root with its smallest child until the parent is smaller than both children or until the new root reaches a leaf node.

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 Min-Heap as:

Min-Heap Data Structure
The element to be deleted is root, i.e. 13.

Process:

The last element is 100.

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

Min-Heap Data Structure
Step 2: Heapify root.

Final Heap:

Min-Heap Data Structure

Implementation of Deletion operation in Min-Heap:

C++

#include <iostream>
#include <vector>

using namespace std;

// Function to insert a new element into the min-heap
void insert_min_heap(vector<int>& heap, int value)
{
    // Add the new element to the end of the heap
    heap.push_back(value);
    // Get the index of the last element
    int index = heap.size() - 1;
    // Compare the new element with its parent and swap if
    // necessary
    while (index > 0
           && heap[(index - 1) / 2] > heap[index]) {
        swap(heap[index], heap[(index - 1) / 2]);
        // Move up the tree to the parent of the current
        // element
        index = (index - 1) / 2;
    }
}

// Function to delete a node from the min-heap
void delete_min_heap(vector<int>& heap, int value)
{
    // Find the index of the element to be deleted
    int index = -1;
    for (int i = 0; i < heap.size(); i++) {
        if (heap[i] == value) {
            index = i;
            break;
        }
    }
    // If the element is not found, return
    if (index == -1) {
        return;
    }
    // Replace the element to be deleted with the last
    // element
    heap[index] = heap[heap.size() - 1];
    // Remove the last element
    heap.pop_back();
    // Heapify the tree starting from the element at the
    // deleted index
    while (true) {
        int left_child = 2 * index + 1;
        int right_child = 2 * index + 2;
        int smallest = index;
        if (left_child < heap.size()
            && heap[left_child] < heap[smallest]) {
            smallest = left_child;
        }
        if (right_child < heap.size()
            && heap[right_child] < heap[smallest]) {
            smallest = right_child;
        }
        if (smallest != index) {
            swap(heap[index], heap[smallest]);
            index = smallest;
        }
        else {
            break;
        }
    }
}

// Main function to test the insert_min_heap and
// delete_min_heap functions
int main()
{
    vector<int> heap;
    int values[] = { 13, 16, 31, 41, 51, 100 };
    int n = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        insert_min_heap(heap, values[i]);
    }
    cout << "Initial heap: ";
    for (int j = 0; j < heap.size(); j++) {
        cout << heap[j] << " ";
    }
    cout << endl;

    delete_min_heap(heap, 13);
    cout << "Heap after deleting 13: ";
    for (int j = 0; j < heap.size(); j++) {
        cout << heap[j] << " ";
    }
    cout << endl;

    return 0;
}

Java

import java.util.*;

public class GFG {
    // Function to insert a new element into the min-heap
    public static void insertMinHeap(List<Integer> heap,
                                     int value)
    {
        // Add the new element to the end of the heap
        heap.add(value);
        // Get the index of the last element
        int index = heap.size() - 1;
        // Compare the new element with its parent and swap
        // if necessary
        while (index > 0
               && heap.get((index - 1) / 2)
                      > heap.get(index)) {
            Collections.swap(heap, index, (index - 1) / 2);
            // Move up the tree to the parent of the current
            // element
            index = (index - 1) / 2;
        }
    }

    // Function to delete a node from the min-heap
    public static void deleteMinHeap(List<Integer> heap,
                                     int value)
    {
        // Find the index of the element to be deleted
        int index = -1;
        for (int i = 0; i < heap.size(); i++) {
            if (heap.get(i) == value) {
                index = i;
                break;
            }
        }
        // If the element is not found, return
        if (index == -1) {
            return;
        }
        // Replace the element to be deleted with the last
        // element
        heap.set(index, heap.get(heap.size() - 1));
        // Remove the last element
        heap.remove(heap.size() - 1);
        // Heapify the tree starting from the element at the
        // deleted index
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;
            if (leftChild < heap.size()
                && heap.get(leftChild)
                       < heap.get(smallest)) {
                smallest = leftChild;
            }
            if (rightChild < heap.size()
                && heap.get(rightChild)
                       < heap.get(smallest)) {
                smallest = rightChild;
            }
            if (smallest != index) {
                Collections.swap(heap, index, smallest);
                index = smallest;
            }
            else {
                break;
            }
        }
    }

    // Main function to test the insertMinHeap and
    // deleteMinHeap functions
    public static void main(String[] args)
    {
        List<Integer> heap = new ArrayList<Integer>();
        int[] values = { 13, 16, 31, 41, 51, 100 };
        int n = values.length;
        for (int i = 0; i < n; i++) {
            insertMinHeap(heap, values[i]);
        }
        System.out.print("Initial heap: ");
        for (int j = 0; j < heap.size(); j++) {
            System.out.print(heap.get(j) + " ");
        }
        System.out.println();

        deleteMinHeap(heap, 13);
        System.out.print("Heap after deleting 13: ");
        for (int j = 0; j < heap.size(); j++) {
            System.out.print(heap.get(j) + " ");
        }
        System.out.println();
    }
}

Python3

def insert_min_heap(heap, value):
    heap.append(value)
    index = len(heap) - 1
    while index > 0 and heap[(index - 1) // 2] > heap[index]:
        heap[index], heap[(index - 1) //
                          2] = heap[(index - 1) // 2], heap[index]
        index = (index - 1) // 2


def delete_min_heap(heap, value):
    index = -1
    for i in range(len(heap)):
        if heap[i] == value:
            index = i
            break
    if index == -1:
        return
    heap[index] = heap[-1]
    heap.pop()
    while True:
        left_child = 2 * index + 1
        right_child = 2 * index + 2
        smallest = index
        if left_child < len(heap) and heap[left_child] < heap[smallest]:
            smallest = left_child
        if right_child < len(heap) and heap[right_child] < heap[smallest]:
            smallest = right_child
        if smallest != index:
            heap[index], heap[smallest] = heap[smallest], heap[index]
            index = smallest
        else:
            break


heap = []
values = [13, 16, 31, 41, 51, 100]
for value in values:
    insert_min_heap(heap, value)
print("Initial heap:", heap)

delete_min_heap(heap, 13)
print("Heap after deleting 13:", heap)

using System;
using System.Collections.Generic;

class MinHeap {
    private List<int> heap = new List<int>();

    public void Insert(int value)
    {
        heap.Add(value);
        int index = heap.Count - 1;
        while (index > 0
               && heap[(index - 1) / 2] > heap[index]) {
            Swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void Delete(int value)
    {
        int index = heap.IndexOf(value);
        if (index == -1) {
            return;
        }
        heap[index] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;
            if (leftChild < heap.Count
                && heap[leftChild] < heap[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < heap.Count
                && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }
            if (smallest != index) {
                Swap(index, smallest);
                index = smallest;
            }
            else {
                break;
            }
        }
    }

    private void Swap(int i, int j)
    {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void Print()
    {
        for (int i = 0; i < heap.Count; i++) {
            Console.Write(heap[i] + " ");
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args)
    {
        MinHeap heap = new MinHeap();
        int[] values = { 13, 16, 31, 41, 51, 100 };
        for (int i = 0; i < values.Length; i++) {
            heap.Insert(values[i]);
        }
        Console.Write("Initial heap: ");
        heap.Print();

        heap.Delete(13);
        Console.Write("Heap after deleting 13: ");
        heap.Print();
    }
}

Javascript

function insertMinHeap(heap, value) {
  // Add the new element to the end of the heap
  heap.push(value);
  // Get the index of the last element
  let index = heap.length - 1;
  // Compare the new element with its parent and swap if necessary
  for (let flr = Math.floor((index - 1) / 2); index > 0 && heap[flr] > heap[index]; flr = Math.floor((index - 1) / 2)) {
    [heap[index], heap[flr]] = [
      heap[flr],
      heap[index],
    ];
    // Move up the tree to the parent of the current element
    index = Math.floor((index - 1) / 2);
  }
}

function deleteMinHeap(heap, value) {
  // Find the index of the element to be deleted
  let index = -1;
  for (let i = 0; i < heap.length; i++) {
    if (heap[i] == value) {
      index = i;
      break;
    }
  }
  // If the element is not found, return
  if (index == -1) {
    return;
  }
  // Replace the element to be deleted with the last element
  heap[index] = heap[heap.length - 1];
  // Remove the last element
  heap.pop();
  // Heapify the tree starting from the element at the deleted index
  while (true) {
    let left_child = 2 * index + 1;
    let right_child = 2 * index + 2;
    let smallest = index;
    if (left_child < heap.length && heap[left_child] < heap[smallest]) {
      smallest = left_child;
    }
    if (right_child < heap.length && heap[right_child] < heap[smallest]) {
      smallest = right_child;
    }
    if (smallest != index) {
      [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
      index = smallest;
    } else {
      break;
    }
  }
}

// Main function to test the insertMinHeap and deleteMinHeap functions
let heap = [];
let values = [13, 16, 31, 41, 51, 100];
for (let i = 0; i < values.length; i++) {
  insertMinHeap(heap, values[i]);
}
console.log("Initial heap: " + heap.join(" "));

deleteMinHeap(heap, 13);
console.log("Heap after deleting 13: " + heap.join(" "));

Output

Initial heap: 13 16 31 41 51 100 
Heap after deleting 13: 16 41 31 100 51

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

Introduction to Min-Heap – Data Structure and Algorithm Tutorials

A Min-Heap is defined as a type of Heap Data Structure in which each node is smaller 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 Min-Heap – Data Structure and Algorithm Tutorials

Purpose and Use Cases of Min-Heap:

Implementing Priority Queue: One of the primary uses of the heap data structure is for implementing priority queues.
Dijkstra’s Algorithm: Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between two nodes in a graph. A min heap can be used to keep track of the unvisited nodes with the smallest distance from the source node.
Sorting: A min heap can be used as a sorting algorithm to efficiently sort a collection of elements in ascending order.
Median finding: A min heap can be used to efficiently find the median of a stream of numbers. We can use one min heap to store the larger half of the numbers and one max heap to store the smaller half. The median will be the root of the min heap.

Deletion in Min-Heap Data Structure

Implementation of Deletion operation in Min-Heap:

Introduction to Min-Heap – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us