Heap Sort (2016)

Mechanism

1. Build a Max-Heap from the input array (heapify) — O(n)
2. Repeatedly: swap the root (maximum element) with the last element of the heap, reduce heap size by 1, and "sift down" (heapify) the new root — repeat n-1 times

Pseudocode

HEAP_SORT(arr):
  BUILD_MAX_HEAP(arr)
  FOR i = n-1 DOWNTO 1:
    SWAP(arr[0], arr[i])
    HEAPIFY(arr, 0, i)  // restore heap property on reduced heap

Complexity

• Time: O(n log n) in all cases (best, average, worst) — like Merge Sort, no worst-case degradation
• Space: O(1) — in-place, unlike Merge Sort's O(n) — this is Heap Sort's key advantage
• Not stable

Heap Sort vs Merge Sort vs Quick Sort (the classic 3-way comparison)

Exam Angle

Heap Sort is the answer whenever a question asks for an algorithm with guaranteed O(n log n) AND O(1) space — it's the only one of the three offering both. Requires understanding of the Heap data structure (complete binary tree stored as array) as a prerequisite.

📌 Sample & Repeated FPSC Questions (2016–2026)

2016, Paper I, Q5(c) (6 marks) — Draw the array A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7} as a binary tree, apply Build-Max-Heap, then show the Heap-Sort execution by rewriting the array after each iteration.

Build-Max-Heap (heapify from last internal node, index 4, down to 0):

Start:            [8, 14, 2, 26, 10, 12, 16, 28, 20, 7]
i=4 (val 10): child 7          → 10>7, no change
i=3 (val 26): children 28,20   → swap with 28 → [8,14,2,28,10,12,16,26,20,7]
i=2 (val 2):  children 12,16   → swap with 16 → [8,14,16,28,10,12,2,26,20,7]
i=1 (val 14): children 28,10   → swap with 28, then sift 14 down past 26
                                → [8,28,16,26,10,12,2,14,20,7]
i=0 (val 8):  children 28,16   → swap with 28, sift 8 down past 26, then past 20
                                → [28,26,16,20,10,12,2,14,8,7]

Final Max-Heap (array + tree):

Array: [28, 26, 16, 20, 10, 12, 2, 14, 8, 7]

              28
           /      \
         26        16
        /  \      /  \
      20   10   12    2
     /  \
   14    8
   /
  7

Heap-Sort execution (swap root with last live element, shrink heap by 1, sift-down new root — array shown after each iteration, sorted tail growing on the right):

[28,26,16,20,10,12,2,14,8,7]  ← start
[26,20,16,14,10,12,2,7,8 | 28]
[20,14,16,8,10,12,2,7 | 26,28]
[16,14,12,8,10,7,2 | 20,26,28]
[14,10,12,8,2,7 | 16,20,26,28]
[12,10,7,8,2 | 14,16,20,26,28]
[10,8,7,2 | 12,14,16,20,26,28]
[8,2,7 | 10,12,14,16,20,26,28]
[7,2 | 8,10,12,14,16,20,26,28]
[2 | 7,8,10,12,14,16,20,26,28]

Final sorted array: [2, 7, 8, 10, 12, 14, 16, 20, 26, 28]

Key reasoning points:

• This is the fully-worked version of the page's HEAP_SORT pseudocode: BUILD_MAX_HEAP costs O(n), then each of the n−1 swap-and-sift-down iterations costs O(log n) — giving the page's stated O(n log n) total, achieved in place (the | above just marks the shrinking-heap / growing-sorted-tail boundary within the same array, not extra memory) — the O(1) space advantage this page's comparison table highlights over Merge Sort.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q5(c) · 6 marks

Q. Draw the array A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7} as a binary tree. Apply Build-Heap to make a Max-Heap (show tree and array). Then show Heap-Sort, rewriting the array after each iteration.

Ans.

• Initial tree (array index i has children 2i and 2i+1):

           8
        /     \
     14         2
    /  \       /  \
  26    10    12   16
 /  \   /
28  20 7

• Build-Heap (heapify from index 5 down to 1):
  • i=5 (10): child 7 is smaller, no change
  • i=4 (26): larger child 28 → swap
  • i=3 (2): larger child 16 → swap
  • i=2 (14): child 28 → swap, then 14 sinks below 26 (swap with 26)
  • i=1 (8): swaps with 28, then 26, then 20
• Max-heap array: [28, 26, 16, 20, 10, 12, 2, 14, 8, 7]

          28
       /      \
     26        16
    /  \      /  \
  20   10    12   2
 /  \   /
14   8 7

• Heap-Sort: swap the root with the last element, reduce the heap size by 1, then heapify the root. The sorted part is on the right.

• Final sorted array: 2 7 8 10 12 14 16 20 26 28. Time O(n log n).