Heap Operations: Heapify, Insertion, and Deletion

Binary Heap par perform hone wale teen primary building-block operations hote hain: Heapify, Insert, aur Extract-Max / Extract-Min (Deletion).

1. Max-Heapify Algorithm – O(log n)

Heapify ek aisi procedure hai jo kisi subtree ke root ko tab tak niche shift (bubble-down) karti hai jab tak heap property satisfy na ho jaye.

MAX_HEAPIFY(A, n, i)
1. largest = i, left = 2*i + 1, right = 2*i + 2
2. If left < n and A[left] > A[largest]: largest = left
3. If right < n and A[right] > A[largest]: largest = right
4. If largest != i then:
       Swap(A[i], A[largest])
       MAX_HEAPIFY(A, n, largest)

2. Building a Heap from Unsorted Array – O(n)

Leaf nodes (indices n/2 se n-1) already trivially heap hote hain. Isliye hum last non-leaf node (i = n/2 - 1) se lekar root (i = 0) tak bottom-up heapify call karte hain:

BUILD_MAX_HEAP(A, n)
1. For i = (n/2 - 1) down to 0 do:
2.     MAX_HEAPIFY(A, n, i)

Mathematical Note: Build Heap ki aggregate time complexity O(n) linear hoti hai, na ki O(n log n), kyunki majority nodes bottom levels par hote hain jahan heapify path short hota hai.

3. Insertion and Deletion

• Insert: Naya element array ke end me add karein aur use parent se compare karte hue upar bubble-up (percolate-up) karein. Time: O(log n).
• Extract-Max (Delete Root): Root element (A[0]) ko save karein, array ke last element ko root par copy karein, size decrement karein, aur root par MAX_HEAPIFY(A, n, 0) call karein. Time: O(log n).

Agli post me hum cover karenge B-Tree: Properties, Structure, and Insertion.