Heap Insertion and Deletion

Heap Insertion and Deletion

In a heap, the Insertion and Deletion operations are crucial because they ensure the heap property is maintained after adding or removing elements. These operations are fundamental in algorithms like Heap Sort, Priority Queues, and Dijkstra's Shortest Path. Let's go through both operations in detail.

1. Heap Insertion (Insert a New Element)

When you insert a new element into a heap, you must ensure that the heap property (whether max-heap or min-heap) is maintained after the insertion. The steps for inserting a new element are as follows:

Steps for Insertion:

1. Add the Element to the End:

   • Insert the new element at the end of the heap (the next available position in the complete binary tree). This ensures that the heap remains a complete binary tree.

2. Bubble Up (or Sift Up):

   • After adding the element at the end, bubble it up (or sift it up) to restore the heap property.
   • Start by comparing the newly inserted element with its parent. If the heap property is violated (i.e., the new element is greater than its parent in a max-heap or smaller than its parent in a min-heap), swap the element with its parent.
   • Continue this process until the element is in the correct position or you reach the root.

Time Complexity:

• O(log n), because, in the worst case, the element needs to bubble up from the leaf to the root, and the height of the heap is log n.

Example of Heap Insertion (Max-Heap):

Suppose we have the following max-heap and want to insert 12:

        20
       /  \
     15    10
    /  \   /
   8   6  5

1. Insert 12 at the end of the heap:

        20
       /  \
     15    10
    /  \   / \
   8   6  5  12
   

2. Bubble up 12:

   • Compare 12 with its parent 10. Since 12 > 10, swap them:

        20
       /  \
     15    12
    /  \   / \
   8   6  5  10
   

3. Bubble up 12 again:

   • Compare 12 with its new parent 15. Since 12 < 15, stop. No more swaps are needed.

The final max-heap after insertion:

        20
       /  \
     15    12
    /  \   / \
   8   6  5  10

2. Heap Deletion (Delete the Root)

Heap deletion typically refers to the operation where you remove the root element from the heap (either the maximum element in a max-heap or the minimum element in a min-heap) and then restore the heap property. In a max-heap, the root is the maximum element, while in a min-heap, it is the minimum element.

Steps for Deletion:

1. Swap the Root with the Last Element:

   • The root of the heap is the element that you want to delete. To remove it, swap the root element with the last element in the heap (the rightmost leaf).
   • This swap places the element to be deleted at the end of the heap.

2. Remove the Last Element:

   • After swapping, remove the last element (which was originally the root).

3. Heapify the Root:

   • Now that the root has been replaced with the last element, the heap property is likely violated. You need to restore the heap property by heapifying the root.
   • Start by comparing the new root with its children. If the heap property is violated (i.e., the root is smaller than its largest child in a max-heap or larger than its smallest child in a min-heap), swap the root with the larger (or smaller) child.
   • Continue heapifying down the tree until the heap property is restored.

Time Complexity:

• O(log n), because after the swap, we need to heapify the tree starting from the root. Heapifying takes O(log n) time as it involves moving down the tree from the root to the leaf, and the height of the tree is log n.

Example of Heap Deletion (Max-Heap):

Consider the following max-heap:

        20
       /  \
     15    10
    /  \   /
   8   6  5

1. Swap the root with the last element:

   • Swap 20 with 5:

        5
       /  \
     15    10
    /  \   /
   8   6  20
   

2. Remove the last element (which is now 20):

        5
       /  \
     15    10
    /  \   
   8   6
   

3. Heapify the root (5):

   • Compare 5 with its children (15 and 10). Since 15 is the largest child, swap 5 and 15:

        15
       /  \
     5     10
    /  \   
   8    6
   

   • Heapify the subtree rooted at index 1 (node 5):
     • Compare 5 with its children (8 and 6). Since 8 is the largest child, swap 5 and 8:

        15
       /  \
     8     10
     

   / \
   5 6

The final max-heap after deletion:

        15
       /  \
     8     10
    /  \   
   5    6

Summary of Heap Insertion and Deletion

• Insertion:

  • Steps: Add the element at the end → Bubble up (sift up) to restore the heap property.
  • Time Complexity: O(log n), because the element may need to bubble up to the root.

• Deletion:

  • Steps: Swap the root with the last element → Remove the last element → Heapify the root to restore the heap property.
  • Time Complexity: O(log n), because the heapify operation works by traversing the height of the tree.

Applications of Heap Insertion and Deletion:

• Priority Queues: Insertion and deletion operations are fundamental in implementing priority queues, where the root element is always the element with the highest (or lowest) priority.
• Heap Sort: In heap sort, both insertion and deletion operations are used to extract the maximum or minimum elements from the heap and build the sorted array.
• Dijkstra’s Shortest Path: Priority queues (using heaps) are used to select the next node with the smallest tentative distance.

Conclusion:

Heap insertion and deletion are both logarithmic-time operations that maintain the heap property, ensuring that the heap is always a complete binary tree and that the root element is always the largest (in a max-heap) or smallest (in a min-heap). These operations are essential for applications like heap sort, priority queues, and other graph algorithms.