Deletion in Heap

Deleting an element from a heap involves removing an element and restoring the heap property.

In a max heap, the element with the highest value is always at the root of the heap. When we want to delete this element, we replace it with the last element in the heap and then perform a process called heapify down to restore the heap property.

Heapify down works by comparing the element at the root with its children and swapping it with the child that has the highest value. This process is repeated recursively until the heap property is satisfied.

Here is an example Java implementation of the deleteMax() method in a MaxHeap class:

1class MaxHeap {
2  private int[] heapArray;
3  private int heapSize;
4
5  public MaxHeap(int[] array) {
6    heapArray = array;
7    heapSize = array.length;
8    buildHeap();
9  }
10
11  public void deleteMax() {
12    if (isEmpty()) {
13      System.out.println("Heap is empty. Cannot delete.");
14    } else {
15      heapArray[0] = heapArray[heapSize - 1];
16      heapSize--;
17      heapifyDown(0);
18    }
19  }
20
21  // Other methods...
22}

In the example code, we have a MaxHeap class with an array heapArray to store the elements. The deleteMax() method checks if the heap is empty. If the heap is not empty, the root element (element with the highest value) is replaced with the last element in the array (heapArray[0] = heapArray[heapSize - 1]) and heapifyDown() is called to restore the heap property.

The heapifyDown(index) method compares the element at the given index with its children and swaps it with the child that has the highest value. This process continues recursively until the heap property is satisfied.

By performing the heapify down operation after deleting the root element, we can ensure that the heap property is maintained and the next highest element is at the root of the heap.