{"title":"Heap Sort","description":"","content":"Heap Sort is a comparison-based sorting algorithm that uses 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.\n\nA heap allows efficient access to the largest or smallest element, so each extraction step runs in O(log n). This produces a consistent time complexity of O(n log n), regardless of the input.\n\n\n\n\n\nHeap Sort is not stable, but it is in-place and does not require extra memory like Merge Sort, which makes it useful in memory-constrained environments.\n\nThis chapter covers how heaps work, how to build and maintain them, and how Heap Sort uses these operations to sort an array.\n\n---\n\n# What Is Heap Sort?\n\nThe core idea: if the maximum element can be found and removed efficiently, the array can be sorted by repeatedly extracting the max and placing it at the end. This depends on the underlying data structure, the heap.\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\nA binary heap does not need pointers or tree nodes. A simple array stores 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). The node at index 1 has children at indices 3 and 4. The flat array encodes the tree structure implicitly, with no extra memory or pointer overhead.\n\nThis array-based representation is what makes heap sort an in-place algorithm. The input array itself is rearranged into a heap and then sorted, 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\nEach phase in detail:\n\n### Phase 1: Build the Max-Heap\n\nThe input array must be rearranged to satisfy the max-heap property. The key operation 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 reaches a leaf.\n\nBuilding the entire heap calls 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 because they have no children that could violate the heap property. The build phase starts 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?** Starting from the root and working down would require each heapify call to push elements through the entire height of the tree. Starting from the bottom means most nodes are near the leaves where the tree is short, which is why building a heap takes O(n) time instead of O(n log n). The Complexity Analysis section derives this in detail.\n\n### Phase 2: Extract Elements\n\nOnce the max-heap is built, 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\nEach swap moves 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 does the core comparison-and-swap work: it compares a node with its children, swaps with the largest if needed, and recurses down the tree. The `heapSort` function orchestrates the build phase and the extraction phase.\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nTrace heap sort on 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 swap 4 and 10.\n\nArray becomes: `[10, 4, 3, 5, 1]`\n\nRecurse on index 1 (where 4 landed). Node 4 has children 5 (index 3) and 1 (index 4). The largest is 5, so 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 input causes degradation; performance is the same for every input |\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\nA naive analysis counts n/2 heapify calls, each O(log n), giving O(n log n). That bound is loose because it ignores where the calls happen in the tree.\n\nMost nodes are near the bottom of the tree, where heapify does 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\nThe extraction phase performs 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 can travel all the way down to the leaves. The total is O(n log n).\n\n### Stability\n\nHeap sort is not stable. Both phases swap elements across long distances. During the build phase, sift-down moves a node down through several levels, jumping past unrelated elements. During the extraction phase, the root swaps with the last heap element before re-heapifying, which can leap one equal element over another.\n\nFor example, with the input `[2, 5a, 5b, 1]`, after building the max-heap the structure becomes something like `[5a, 2, 5b, 1]` or `[5b, 5a, 2, 1]` depending on the heapify path. Subsequent extractions place the values back into the array in the order they exit the heap, which is not guaranteed to match the original `5a, 5b` order.\n\nA stable variant is possible by tagging each element with its original index and using that as a tiebreaker in the heap comparison, but this adds O(n) auxiliary space and forfeits heap sort's main advantage over merge sort.\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. For workloads that cannot tolerate O(n^2) on adversarial inputs, heap sort is a 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 only the k largest or smallest elements are needed, the extraction phase can stop early after k iterations, giving O(n + k log n) time. Priority queues use this property for top-k selection.\n- **Embedded systems or real-time constraints.** Predictable performance with minimal memory fits 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's partition scans access elements sequentially, which fits CPU cache prefetch behavior.\n- **Stable sorting.** Heap sort is not stable. Merge sort or Timsort is a better choice when equal elements must retain their original order.\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 fits.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium