🗑️ Deletion in Heap Tree (Max/Min Heap)

Follow Me

Definition:
In a Heap Tree, deletion typically refers to removing the root node (Max in Max Heap, Min in Min Heap). The last element is moved to the root, and then heapify-down is performed to restore the heap property.

📌 Steps for Deletion (Max Heap Example)

Remove the root (e.g., max element).
Move the last element to the root position.
Heapify-down: Compare with children and swap with the larger one (in Max Heap).
Repeat until the heap property is restored.

📊 Basic Diagram (Delete root from Max Heap)

Before Deletion (Max Heap):

         60
       /     \
     30     50
     /  \      /
  10 20  40

Step 1: Remove root (60)

Step 2: Move last element (40) to root

Step 3: Heapify-down
(Compare 40 with children → 50 is largest → Swap)

Heap property restored ✅

🧠 Python Code Example for Deletion in Max Heap

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def delete(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()  # Move last to root
        self._heapify_down(0)
        return root

    def _heapify_up(self, index):
        parent = (index - 1) // 2
        if index > 0 and self.heap[index] > self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)

    def _heapify_down(self, index):
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

    def display(self):
        print("Heap:", self.heap)

# Example usage
h = MaxHeap()
for value in [60, 30, 50, 10, 20, 40]:
    h.insert(value)
h.display()
h.delete()
h.display()