Heap Push and Pop Operations

1. Heap Overview

A heap is a complete binary tree where:

• Min-Heap: Each parent ≤ children (root is the minimum).
• Max-Heap: Each parent ≥ children (root is the maximum). Heaps are typically implemented as arrays for efficiency.

2. Heap Push (Insertion)

Steps:

1. Add to End: Insert the new value at the next available position (end of the array).
2. Percolate Up:
   • Compare the new value with its parent.
   • If it violates the heap property (e.g., smaller than parent in a min-heap), swap them.
   • Repeat until the heap property is restored.

Example (Min-Heap):

Insert 17 into the heap:

Initial Heap: [ -, 14, 19, 16, 21, 26, 19, 68, 65, 30 ]
Insert 17   → [ -, 14, 19, 16, 21, 26, 19, 68, 65, 30, <u>17</u> ]

Percolate Up:
17 swaps with 26 (index 5 → 2) → 17 swaps with 19 (index 2 → 1)
Final Heap:   [ -, 14, <u>17</u>, 16, 21, 19, 19, 68, 65, 30, 26 ]

Time Complexity: O(log n) (height of the tree).

3. Heap Pop (Removal)

Steps:

1. Remove Root: Extract the root (min/max value).
2. Replace with Last Element: Move the last array element to the root.
3. Percolate Down:
   • Compare the new root with its children.
   • Swap with the smaller child (min-heap) or larger child (max-heap).
   • Repeat until the heap property is restored.