🗑️ 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)

1. Remove the root (e.g., max element).

2. Move the last element to the root position.

3. Heapify-down: Compare with children and swap with the larger one (in Max Heap).

4. 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

40 / \ 30 50 / \ 10 20

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

50 / \ 30 40 / \ 10 20

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()