Min Heap Deletion Algorithm with Example
Page 1: Introduction to Min Heap Deletion
A Min Heap is a complete binary tree where the value of each node is less than or equal
to the values of its children. The smallest element is always at the root of the heap. The
deletion operation in a Min Heap typically refers to removing the minimum element,
which is the root node.
This operation is fundamental for applications like priority queues and heapsort. The
process involves removing the root, replacing it with the last element in the heap, and
then restoring the heap property by percolating down the new root.
Page 2: The Min Heap Deletion Algorithm
The algorithm for deleting the minimum element (the root) from a Min Heap proceeds as
follows:
1. Check if the heap is empty: If the heap is empty, an error or appropriate
message should be returned.
2. Replace the root: Store the value of the root node (the minimum element) to be
returned later. Then, replace the root with the last element in the heap.
3. Remove the last element: Decrease the size of the heap by one, effectively
removing the last element from its original position.
4. Heapify down (Percolate down): Starting from the new root, compare its value
with its children. If the root's value is greater than either of its children, swap it
with the smaller child. Repeat this process with the swapped node until the heap
property is restored (i.e., the node is smaller than or equal to both its children, or
it becomes a leaf node).
Page 3: Example - Initial State and First Steps
Let's consider the following Min Heap:
Initial Min Heap:
3
/ \
5 7
/ \ / \
9 10 8 12
We want to delete the minimum element, which is 3.
Step 1: Remove the root (3) and store it.
Step 2: Replace the root with the last element, which is 12.
Step 3: Decrease the heap size. The heap now conceptually looks like this:
12
/ \
5 7
/ \ /
9 10 8
Step 4: Heapify down the new root (12).
Compare 12 with its children, 5 and 7. Since 5 is the smaller child, swap 12 and 5.
5
/ \
12 7
/ \ /
9 10 8
Page 4: Example - Continuing the Heapify Down
The element 12 is now at the position where 5 was. We continue heapifying down from
this new position of 12.
Compare 12 with its children, 9 and 10. Since 9 is the smaller child, swap 12 and 9.
5
/ \
9 7
/ \ /
12 10 8
The element 12 is now at the position where 9 was. 12 has no children, so the heap
property is satisfied at this point. The deletion is complete.
Final Min Heap after deletion:
5
/ \
9 7
/ \
12 10
Page 5: Summary and Complexity
The deletion of the minimum element from a Min Heap involves replacing the root with
the last element and then performing a 'heapify down' operation. This ensures that the
tree structure remains a Min Heap after the removal.
Time Complexity:
The 'heapify down' operation takes logarithmic time with respect to the number of nodes
in the heap, as it traverses the height of the tree. If 'n' is the number of nodes in the
heap, the height of the tree is O(log n). Therefore, the time complexity for deleting the
minimum element is O(log n).
This efficiency makes Min Heaps a suitable data structure for various algorithms
requiring frequent extraction of the minimum element.
