{"title":"Chapter 7: Heap Sort","description":"","content":"Heap Sort is a comparison-based sorting algorithm that leverages the properties of a heap, a specialized binary tree structure. It first builds a heap from the input array, then repeatedly extracts the maximum (or minimum) element and places it at its correct position in the array.\n\nThe key idea is that a heap allows efficient access to the largest or smallest element, making each extraction step fast. This leads to a consistent time complexity of O(n log n), regardless of the input.\n\nHeap Sort is not stable, but it is in-place and does not require extra memory like Merge Sort, making it useful in memory-constrained environments.\n\nIn this chapter, you will learn how heaps work, how to build and maintain them, and how Heap Sort uses these operations to sort an array efficiently.\n\n---\n\n# What Is Heap Sort?\n\nHeap sort is a comparison-based sorting algorithm that uses a binary heap to organize elements. The core idea is simple: if you can efficiently find and remove the maximum element, you can sort an array by repeatedly extracting the max and placing it at the end.\n\nBefore diving into the algorithm, let us make sure the underlying data structure is clear.\n\n### The Max-Heap Property\n\nA **max-heap** is a complete binary tree where every parent node is greater than or equal to its children. The root of the tree always holds the largest element. This property applies recursively, so every subtree is also a valid max-heap.\n\nHere is what a max-heap looks like:\n\n\n```mermaid\ngraph TD\n A[\"10\"] --> B[\"5\"]\n A --> C[\"3\"]\n B --> D[\"4\"]\n B --> E[\"1\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe root (10) is larger than both children (5, 3). Node 5 is larger than both of its children (4, 1). Every parent dominates its children, which is exactly the max-heap property.\n\n### Array Representation\n\nThe beauty of a binary heap is that you do not need pointers or tree nodes. A simple array does the job. You store the tree level by level, left to right. For any element at index `i`:\n\n- **Parent** is at index `(i - 1) / 2`\n- **Left child** is at index `2 * i + 1`\n- **Right child** is at index `2 * i + 2`\n\nThe tree above maps to an array like this:\n\n\n```mermaid\ngraph LR\n subgraph \"Array Representation\"\n I0[\"Index 0
10\"]\n I1[\"Index 1
5\"]\n I2[\"Index 2
3\"]\n I3[\"Index 3
4\"]\n I4[\"Index 4
1\"]\n end\n\n style I0 fill:#00ceff,stroke:#000,color:#000\n style I1 fill:#ffa94d,stroke:#000,color:#000\n style I2 fill:#ffa94d,stroke:#000,color:#000\n style I3 fill:#38d9a9,stroke:#000,color:#000\n style I4 fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nIndex 0 holds the root (10). Its left child is at index 1 (value 5), and its right child is at index 2 (value 3). Node at index 1 has children at indices 3 and 4. No extra memory, no pointer overhead. Just a flat array with implicit tree structure.\n\nThis array-based representation is what makes heap sort an in-place algorithm. We rearrange the input array itself into a heap, then sort it, all without allocating additional storage.\n\n---\n\n# How Heap Sort Works\n\nThe algorithm has two main phases:\n\n1. **Build a max-heap** from the unsorted array\n2. **Extract elements** one by one from the heap to produce the sorted order\n\nLet us look at each phase in detail.\n\n### Phase 1: Build the Max-Heap\n\nWe need to rearrange the input array so it satisfies the max-heap property. The key operation here is **heapify** (also called **sift-down**), which takes a node that might violate the heap property and pushes it down to its correct position.\n\n**How heapify works:**\n\n1. Compare the node with its left and right children\n2. If the largest value is not the node itself, swap the node with its largest child\n3. Repeat from the new position until the node is larger than both children or it reaches a leaf\n\nTo build the entire heap, we call heapify on every non-leaf node, starting from the bottom of the tree and working upward. Leaf nodes (the bottom half of the array) are already valid heaps by themselves, they have no children to violate anything. So we start from the last non-leaf node, which is at index `(n / 2) - 1`.\n\n\n```mermaid\nflowchart TD\n A[\"Start from last
non-leaf node
i = n/2 - 1\"]:::primary\n B[\"Call heapify
on node i\"]:::secondary\n C{\"Is i >= 0?\"}:::teal\n D[\"Decrement i\"]:::primary\n E[\"Max-heap
built\"]:::green\n\n A --> C\n C -- \"Yes\" --> B\n B --> D\n D --> C\n C -- \"No\" --> E\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Why bottom-up and not top-down?** If we started from the root and worked down, each heapify call might need to push elements through the entire height of the tree. By starting from the bottom, most nodes are near the leaves where the tree is short. This is why building a heap takes O(n) time instead of O(n log n). We will explain this more in the complexity section.\n\n### Phase 2: Extract Elements\n\nOnce we have a max-heap, the largest element sits at index 0 (the root). To sort the array:\n\n1. **Swap** the root (largest element) with the last element in the heap\n2. **Shrink** the heap size by one (the last element is now in its final sorted position)\n3. **Heapify** the root to restore the max-heap property\n4. **Repeat** until the heap has one element left\n\nEach extraction places the next-largest element at the end of the array. After all extractions, the array is sorted in ascending order.\n\n\n```mermaid\nflowchart TD\n A[\"Max-heap ready\"]:::primary\n B[\"Swap root with
last heap element\"]:::secondary\n C[\"Reduce heap
size by 1\"]:::teal\n D[\"Heapify root\"]:::primary\n E{\"Heap size > 1?\"}:::secondary\n F[\"Array is sorted\"]:::green\n\n A --> B\n B --> C\n C --> D\n D --> E\n E -- \"Yes\" --> B\n E -- \"No\" --> F\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThink of it this way: each swap \"retires\" the largest remaining element to the back of the array. The heap occupies the front portion, and the sorted section grows from the back. Eventually the heap shrinks to nothing and the entire array is sorted.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class HeapSort {\n\n public static void heapSort(int[] arr) {\n int n = arr.length;\n\n // Phase 1: Build max-heap (start from last non-leaf node)\n for (int i = n / 2 - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for (int i = n - 1; i > 0; i--) {\n // Swap root (max) with last element\n int temp = arr[0];\n arr[0] = arr[i];\n arr[i] = temp;\n\n // Heapify the reduced heap\n heapify(arr, i, 0);\n }\n }\n\n private static void heapify(int[] arr, int heapSize, int rootIndex) {\n int largest = rootIndex;\n int left = 2 * rootIndex + 1;\n int right = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest]) {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest != rootIndex) {\n int temp = arr[rootIndex];\n arr[rootIndex] = arr[largest];\n arr[largest] = temp;\n\n heapify(arr, heapSize, largest);\n }\n }\n}\n```\n\n```python\ndef heap_sort(arr):\n n = len(arr)\n\n # Phase 1: Build max-heap\n for i in range(n // 2 - 1, -1, -1):\n heapify(arr, n, i)\n\n # Phase 2: Extract elements one by one\n for i in range(n - 1, 0, -1):\n arr[0], arr[i] = arr[i], arr[0]\n heapify(arr, i, 0)\n\ndef heapify(arr, heap_size, root_index):\n largest = root_index\n left = 2 * root_index + 1\n right = 2 * root_index + 2\n\n if left < heap_size and arr[left] > arr[largest]:\n largest = left\n\n if right < heap_size and arr[right] > arr[largest]:\n largest = right\n\n if largest != root_index:\n arr[root_index], arr[largest] = arr[largest], arr[root_index]\n heapify(arr, heap_size, largest)\n```\n\n```cpp\n#include \n#include \n\nvoid heapify(std::vector& arr, int heapSize, int rootIndex) {\n int largest = rootIndex;\n int left = 2 * rootIndex + 1;\n int right = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest]) {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest != rootIndex) {\n std::swap(arr[rootIndex], arr[largest]);\n heapify(arr, heapSize, largest);\n }\n}\n\nvoid heapSort(std::vector& arr) {\n int n = arr.size();\n\n // Phase 1: Build max-heap\n for (int i = n / 2 - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for (int i = n - 1; i > 0; i--) {\n std::swap(arr[0], arr[i]);\n heapify(arr, i, 0);\n }\n}\n```\n\n```go\npackage main\n\ntype HeapSort struct{}\n\nfunc (HeapSort) Sort(arr []int) {\n\tn := len(arr)\n\n\t// Phase 1: Build max-heap\n\tfor i := n/2 - 1; i >= 0; i-- {\n\t\theapify(arr, n, i)\n\t}\n\n\t// Phase 2: Extract elements one by one\n\tfor i := n - 1; i > 0; i-- {\n\t\tarr[0], arr[i] = arr[i], arr[0]\n\t\theapify(arr, i, 0)\n\t}\n}\n\nfunc heapify(arr []int, heapSize int, rootIndex int) {\n\tlargest := rootIndex\n\tleft := 2*rootIndex + 1\n\tright := 2*rootIndex + 2\n\n\tif left < heapSize && arr[left] > arr[largest] {\n\t\tlargest = left\n\t}\n\n\tif right < heapSize && arr[right] > arr[largest] {\n\t\tlargest = right\n\t}\n\n\tif largest != rootIndex {\n\t\tarr[rootIndex], arr[largest] = arr[largest], arr[rootIndex]\n\t\theapify(arr, heapSize, largest)\n\t}\n}\n```\n\n```csharp\npublic class HeapSort\n{\n public static void Sort(int[] arr)\n {\n int n = arr.Length;\n\n // Phase 1: Build max-heap\n for (int i = n / 2 - 1; i >= 0; i--)\n {\n Heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for (int i = n - 1; i > 0; i--)\n {\n (arr[0], arr[i]) = (arr[i], arr[0]);\n Heapify(arr, i, 0);\n }\n }\n\n private static void Heapify(int[] arr, int heapSize, int rootIndex)\n {\n int largest = rootIndex;\n int left = 2 * rootIndex + 1;\n int right = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest])\n {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest])\n {\n largest = right;\n }\n\n if (largest != rootIndex)\n {\n (arr[rootIndex], arr[largest]) = (arr[largest], arr[rootIndex]);\n Heapify(arr, heapSize, largest);\n }\n }\n}\n```\n\n```rust\npub struct HeapSort;\n\nimpl HeapSort {\n pub fn sort(arr: &mut Vec) {\n let n = arr.len();\n\n // Phase 1: Build max-heap\n for i in (0..n / 2).rev() {\n heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for i in (1..n).rev() {\n arr.swap(0, i);\n heapify(arr, i, 0);\n }\n }\n}\n\nfn heapify(arr: &mut Vec, heap_size: usize, root_index: usize) {\n let mut largest = root_index;\n let left = 2 * root_index + 1;\n let right = 2 * root_index + 2;\n\n if left < heap_size && arr[left] > arr[largest] {\n largest = left;\n }\n\n if right < heap_size && arr[right] > arr[largest] {\n largest = right;\n }\n\n if largest != root_index {\n arr.swap(root_index, largest);\n heapify(arr, heap_size, largest);\n }\n}\n```\n\n```javascript\nfunction heapSort(arr) {\n const n = arr.length;\n\n // Phase 1: Build max-heap\n for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for (let i = n - 1; i > 0; i--) {\n [arr[0], arr[i]] = [arr[i], arr[0]];\n heapify(arr, i, 0);\n }\n}\n\nfunction heapify(arr, heapSize, rootIndex) {\n let largest = rootIndex;\n const left = 2 * rootIndex + 1;\n const right = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest]) {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest !== rootIndex) {\n [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];\n heapify(arr, heapSize, largest);\n }\n}\n```\n\n```typescript\nfunction heapSort(arr: number[]): void {\n const n = arr.length;\n\n // Phase 1: Build max-heap\n for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {\n heapify(arr, n, i);\n }\n\n // Phase 2: Extract elements one by one\n for (let i = n - 1; i > 0; i--) {\n [arr[0], arr[i]] = [arr[i], arr[0]];\n heapify(arr, i, 0);\n }\n}\n\nfunction heapify(arr: number[], heapSize: number, rootIndex: number): void {\n let largest: number = rootIndex;\n const left: number = 2 * rootIndex + 1;\n const right: number = 2 * rootIndex + 2;\n\n if (left < heapSize && arr[left] > arr[largest]) {\n largest = left;\n }\n\n if (right < heapSize && arr[right] > arr[largest]) {\n largest = right;\n }\n\n if (largest !== rootIndex) {\n [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];\n heapify(arr, heapSize, largest);\n }\n}\n```\n\n\nThe `heapify` function is the workhorse. It compares a node with its children, swaps with the largest if needed, and recurses down the tree. The `heapSort` function simply orchestrates the build phase and the extraction phase.\n\n\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through heap sort with the array `[4, 10, 3, 5, 1]`.\n\n### Phase 1: Building the Max-Heap\n\nThe array has 5 elements, so the last non-leaf node is at index `5 / 2 - 1 = 1`.\n\n**Initial array:** `[4, 10, 3, 5, 1]`\n\nThe initial tree looks like this:\n\n\n```mermaid\ngraph TD\n A[\"4 (i=0)\"] --> B[\"10 (i=1)\"]\n A --> C[\"3 (i=2)\"]\n B --> D[\"5 (i=3)\"]\n B --> E[\"1 (i=4)\"]\n\n style A fill:#ff8787,stroke:#000,color:#000\n style B fill:#00ceff,stroke:#000,color:#000\n style C fill:#00ceff,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n**Step 1: Heapify index 1 (value 10)**\n\nNode 10 has children 5 (index 3) and 1 (index 4). Since 10 > 5 and 10 > 1, no swap is needed.\n\nArray after step 1: `[4, 10, 3, 5, 1]` (unchanged)\n\n**Step 2: Heapify index 0 (value 4)**\n\nNode 4 has children 10 (index 1) and 3 (index 2). The largest is 10, so we swap 4 and 10.\n\nArray becomes: `[10, 4, 3, 5, 1]`\n\nNow we recurse on index 1 (where 4 landed). Node 4 has children 5 (index 3) and 1 (index 4). The largest is 5, so we swap 4 and 5.\n\nArray becomes: `[10, 5, 3, 4, 1]`\n\nNode 4 is now at index 3, which is a leaf. Done.\n\nThe max-heap is built:\n\n\n```mermaid\ngraph TD\n A[\"10 (i=0)\"] --> B[\"5 (i=1)\"]\n A --> C[\"3 (i=2)\"]\n B --> D[\"4 (i=3)\"]\n B --> E[\"1 (i=4)\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nEvery parent is now greater than or equal to its children. The max-heap property is satisfied.\n\n### Phase 2: Extracting Elements\n\n**Extraction 1:** Swap root (10) with last element (1). Reduce heap size to 4. Heapify root.\n\n\n```shell\nSwap: [1, 5, 3, 4, | 10] (10 is now in final position)\nHeapify: 1 vs children 5, 3 -> swap with 5 -> [5, 1, 3, 4, | 10]\n 1 vs children 4 -> swap with 4 -> [5, 4, 3, 1, | 10]\n```\n\n\n**Extraction 2:** Swap root (5) with last heap element (1). Reduce heap size to 3. Heapify root.\n\n\n```shell\nSwap: [1, 4, 3, | 5, 10] (5 is now in final position)\nHeapify: 1 vs children 4, 3 -> swap with 4 -> [4, 1, 3, | 5, 10]\n 1 is a leaf -> done\n```\n\n\n**Extraction 3:** Swap root (4) with last heap element (3). Reduce heap size to 2. Heapify root.\n\n\n```shell\nSwap: [3, 1, | 4, 5, 10] (4 is now in final position)\nHeapify: 3 vs child 1 -> 3 > 1, no swap needed\n```\n\n\n**Extraction 4:** Swap root (3) with last heap element (1). Reduce heap size to 1. Done.\n\n\n```shell\nSwap: [1, | 3, 4, 5, 10] (3 is now in final position)\nHeap has 1 element -> done\n```\n\n\n**Final sorted array:** `[1, 3, 4, 5, 10]`\n\nThe pipe character `|` in the traces above separates the active heap (left) from the sorted portion (right). With each extraction, the heap shrinks and the sorted section grows until the entire array is in order.\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| **Best** | O(n log n) | Even if the array is already sorted, heap sort builds the heap and extracts all elements |\n| **Average** | O(n log n) | Each of the n extractions requires a heapify that takes O(log n) |\n| **Worst** | O(n log n) | No pathological inputs. Performance is always the same |\n| **Space** | O(1) | In-place. Only a constant number of variables beyond the input array |\n| **Stable** | No | Equal elements may change their relative order during swaps |\n\n\n### Why Building a Heap Takes O(n)\n\nThis is one of the most commonly asked interview questions about heap sort, and the answer is counterintuitive. You might think: we call heapify n/2 times, and each call takes O(log n), so the total should be O(n log n). But that overestimates the work.\n\nThe key insight is that most nodes are near the bottom of the tree, where heapify does very little work. In a complete binary tree with n nodes:\n\n- About n/2 nodes are leaves (heapify does 0 work)\n- About n/4 nodes are one level above leaves (heapify does at most 1 swap)\n- About n/8 nodes are two levels above (at most 2 swaps)\n- The root is the only node that might need log(n) swaps\n\nThe total work is:\n\n\n```shell\nn/4 * 1 + n/8 * 2 + n/16 * 3 + ... + 1 * log(n)\n= n * (1/4 + 2/8 + 3/16 + ...)\n= n * sum(k / 2^(k+1)) for k = 1 to log(n)\n```\n\n\nThis series converges to a constant (approximately 2), so the total work is O(n).\n\n### Why the Extraction Phase Takes O(n log n)\n\nDuring the extraction phase, we perform n - 1 extractions. Each extraction involves a swap (O(1)) and a heapify from the root (O(log n)). Unlike the build phase, every heapify during extraction starts from the root and might travel all the way down to the leaves. So the total is O(n log n), and there is no shortcut here.\n\n---\n\n# When to Use Heap Sort\n\n### Good for\n\n- **Guaranteed O(n log n) worst case.** Unlike quick sort, heap sort never degrades. If you cannot tolerate O(n^2) performance on adversarial inputs, heap sort is the safe choice.\n- **O(1) extra space.** Unlike merge sort, heap sort does not need auxiliary arrays. When memory is tight, this matters.\n- **Partial sorting.** If you only need the k largest or smallest elements, you can stop the extraction phase early after k iterations, giving you O(n + k log n) time. This is how priority queues power \"top-k\" algorithms.\n- **Embedded systems or real-time constraints.** Predictable performance with minimal memory makes heap sort attractive in resource-constrained environments.\n\n### Not ideal for\n\n- **General-purpose sorting.** In practice, quick sort is faster due to better cache locality. Heap sort jumps around the array (parent to child indices), which causes frequent cache misses on modern hardware. Quick sort, on the other hand, accesses elements sequentially, which plays nicely with CPU caches.\n- **Stable sorting.** Heap sort is not stable. If you need equal elements to retain their original order, merge sort or Timsort is a better choice.\n- **Nearly sorted data.** Insertion sort runs in O(n) on nearly sorted arrays. Heap sort does not benefit from existing order and always takes O(n log n).\n- **Small arrays.** The overhead of heap construction is not worth it for small inputs. Simple algorithms like insertion sort are faster for arrays under 20-30 elements.\n\n### Comparison with Other O(n log n) Sorts\n\n\n| Property | Heap Sort | Merge Sort | Quick Sort |\n|----------|-----------|------------|------------|\n| **Worst-case time** | O(n log n) | O(n log n) | O(n^2) |\n| **Average time** | O(n log n) | O(n log n) | O(n log n) |\n| **Extra space** | O(1) | O(n) | O(log n) stack |\n| **Stable** | No | Yes | No (typically) |\n| **Cache-friendly** | No | Moderate | Yes |\n| **Adaptive** | No | No | Somewhat |\n| **In practice** | Slowest of the three | Good for linked lists | Fastest on average |\n\n\nHeap sort occupies a unique niche: it is the only comparison-based sort that offers both O(n log n) worst-case time and O(1) extra space. When both of those constraints matter simultaneously, heap sort is your best option.","pageType":"dsa"}

Chapter 7: Heap Sort

Ashish Pratap Singh

Get Premium