Heap sort — O(n log n), in-place, not stable

3.6.5 · Coding › Sorting & Searching

---

Heap KYA hota hai?

---

Algorithm KAISE run karta hai

Do phases:

1. Build-max-heap: raw array ko heap mein badlo.
2. Sort-down: $n-1$ baar, root ko last element se swap karo, heap shrink karo, root ko re-heapify karo.

Asli kaam sift-down karta hai (a.k.a. heapify): ek aisa node jiske subtrees already heaps hain lekin uski khud ki value thodi choti ho sakti hai, usse push down karo uske sahi level tak.

sift_down(A, i, n):          # heap occupies A[0..n-1]
    while True:
        l, r = 2i+1, 2i+2
        largest = i
        if l < n and A[l] > A[largest]: largest = l
        if r < n and A[r] > A[largest]: largest = r
        if largest == i: break
        swap(A[i], A[largest])
        i = largest

heap_sort(A):
    n = len(A)
    for i = n//2 - 1 down to 0:   # build heap
        sift_down(A, i, n)
    for end = n-1 down to 1:      # sort
        swap(A[0], A[end])        # crown to the back
        sift_down(A, 0, end)      # re-heapify shrunken heap

![[3.6.05-Heap-sort-—-O(n-log

Concept Map