Lecture 324:- Inserting in a Heap

Insertion in a heap involves adding a new element to the heap while maintaining the heap property. To insert an element in a max heap or min heap, follow these steps:

1. Add the new element at the last available position in the heap.
2. Compare the value of the newly inserted element with its parent (for max heap) or with its children (for min heap).
3. If the heap property is violated (i.e., the element is greater than its parent in a max heap or less than its children in a min heap), swap the element with its parent (for max heap) or with its minimum child (for min heap).
4. Continue this process (also known as "bubble-up" or "percolate-up") until the heap property is restored.

Here's the step-by-step procedure for insertion in a max heap:

Max Heap Insertion:

1. Add the new element at the last available position in the heap (i.e., the leftmost vacant spot in the bottom row of the binary tree).
2. Compare the value of the newly inserted element with its parent.
3. If the value of the new element is greater than its parent's value, swap the elements.
4. Repeat steps 2-3 until the new element's value is no longer greater than its parent's value or until the new element reaches the root (i.e., there is no parent).

Here's the step-by-step procedure for insertion in a min heap:

Min Heap Insertion:

1. Add the new element at the last available position in the heap (i.e., the leftmost vacant spot in the bottom row of the binary tree).
2. Compare the value of the newly inserted element with its parent.
3. If the value of the new element is less than its parent's value, swap the elements.
4. Repeat steps 2-3 until the new element's value is no longer less than its parent's value or until the new element reaches the root (i.e., there is no parent).

The time complexity of inserting an element in a heap is O(log n), where n is the number of elements in the heap. This is because the insertion process involves traversing the height of the heap, which is logarithmic with respect to the number of elements.