Definition
- Heap sort – a comparison-based, in-place sort using a binary max-heap stored directly in the array.
- Build heap – sift down every non-leaf node from the last parent toward the root; this is O(n).
- Sort down – swap the root (maximum) to the end, shrink the heap, sift down the new root; O(n log n) total.
- In-place – uses O(1) extra space; no auxiliary buffer needed.
- Not stable – swapping distant elements can reorder equal keys.
Imagine the National Bank of India arranges transaction amounts into a tournament bracket where every manager holds an amount at least as big as the two people below them, so the biggest amount sits at the top. The clerk takes the top amount (the largest), places it at the end of the sorted list, then lets the replacement sink to its proper level. She repeats until every amount has been extracted in descending order.
Understanding the Concepts
What is heap sort?
Heap sort is a comparison-based sorting algorithm built on a binary max-heap stored directly inside the array. A max-heap ensures that every parent is at least as large as its children, which forces the overall maximum to sit at index zero. The algorithm has two phases: build the heap, then repeatedly extract the maximum.
package com.bank.sort;
import java.util.Arrays;
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// Phase 1: Build max-heap
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// Phase 2: Sort down
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // move max to end
siftDown(arr, i, 0); // restore heap over shrinking range
}
}
private static void siftDown(int[] arr, int heapSize, int parent) {
int largest = parent;
int left = 2 * parent + 1;
int right = 2 * parent + 2;
if (left < heapSize && arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest != parent) {
swap(arr, parent, largest);
siftDown(arr, heapSize, largest);
}
}
private static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
public static void main(String[] args) {
int[] amounts = {50000, 20000, 80000, 10000, 40000, 70000};
heapSort(amounts);
System.out.println("Sorted: " + Arrays.toString(amounts));
}
}
Sorted: [10000, 20000, 40000, 50000, 70000, 80000]
How does the array represent a binary heap?
For an element at index i, its left child is at 2*i + 1, its right child is at 2*i + 2, and its parent is at (i - 1) / 2. No pointers are needed. The heap is a complete binary tree packed into a contiguous array.
package com.bank.sort;
public class HeapIndices {
public static void main(String[] args) {
int[] heap = {80, 50, 70, 20, 40, 10};
System.out.println("Heap array: " + java.util.Arrays.toString(heap));
for (int i = 0; i < heap.length; i++) {
int left = 2 * i + 1;
int right = 2 * i + 2;
System.out.println(" index " + i + " (" + heap[i] + ")"
+ (left < heap.length ? " left=" + heap[left] : "")
+ (right < heap.length ? " right=" + heap[right] : ""));
}
}
}
Heap array: [80, 50, 70, 20, 40, 10]
index 0 (80) left=50 right=70
index 1 (50) left=20 right=40
index 2 (70) left=10
index 3 (20)
index 4 (40)
index 5 (10)
How does sift-down work?
Sift-down takes a node that may violate the heap property, compares it to its larger child, and swaps down repeatedly until the node is at least as large as both children or reaches a leaf.
package com.bank.sort;
public class SiftDownTrace {
static void siftDown(int[] arr, int size, int parent) {
int largest = parent;
int left = 2 * parent + 1;
int right = 2 * parent + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != parent) {
System.out.println(" Swap " + arr[parent] + " with " + arr[largest]);
int t = arr[parent]; arr[parent] = arr[largest]; arr[largest] = t;
siftDown(arr, size, largest);
}
}
public static void main(String[] args) {
int[] arr = {10, 80, 70, 20, 40, 50}; // 10 at root violates
System.out.println("Before: " + java.util.Arrays.toString(arr));
siftDown(arr, arr.length, 0);
System.out.println("After: " + java.util.Arrays.toString(arr));
}
}
Before: [10, 80, 70, 20, 40, 50]
Swap 10 with 80
Swap 10 with 40
After: [80, 40, 70, 20, 10, 50]
Why is build-heap O(n) and not O(n log n)?
Building the heap by sifting down from the last parent toward the root is O(n), not O(n log n). The reason is that most nodes are near the bottom where the sift distance is small. Half the nodes are leaves (zero work), a quarter sift one level, an eighth sift two levels, and so on. The total work sums to O(n).
package com.bank.sort;
public class BuildHeapComplexity {
public static void main(String[] args) {
// For n elements:
// n/2 leaves: 0 sifts each
// n/4 nodes: 1 sift each
// n/8 nodes: 2 sifts each
// Sum: n/4*1 + n/8*2 + n/16*3 + ... = O(n)
System.out.println("Build-heap is O(n), not O(n log n)");
System.out.println("Most nodes are near the bottom with short sift distances.");
}
}
Build-heap is O(n), not O(n log n)
Most nodes are near the bottom with short sift distances.
How does heap sort compare to quick sort and merge sort?
| Feature | Heap Sort | Quick Sort | Merge Sort |
|---|---|---|---|
| Time (worst) | O(n log n) | O(n^2) | O(n log n) |
| Time (avg) | O(n log n) | O(n log n) | O(n log n) |
| Space | O(1) | O(log n) | O(n) |
| Stable | No | No | Yes |
| In-place | Yes | Yes | No |
| Cache | Poor (jumping) | Good (sequential) | Sequential reads |
Why is heap sort not the default despite its guarantees?
Heap sort guarantees O(n log n) in all cases with O(1) space, but its memory-access pattern jumps around the array following parent-child indices. This is cache-unfriendly and makes it slower in practice than quick sort's sequential scans. Quick sort wins for speed; merge sort wins for stability. Heap sort's niche is when you need in-place plus guaranteed O(n log n).
package com.bank.sort;
import java.util.Arrays;
public class HeapVsQuickBenchmark {
public static void main(String[] args) {
int n = 1_000_000;
int[] data = new int[n];
for (int i = 0; i < n; i++) data[i] = (int)(Math.random() * 1_000_000);
// Quick sort (via Arrays.sort)
int[] copy1 = data.clone();
long start = System.nanoTime();
Arrays.sort(copy1);
System.out.println("Arrays.sort: " + (System.nanoTime()-start)/1_000_000 + "ms");
// Heap sort
int[] copy2 = data.clone();
start = System.nanoTime();
heapSort(copy2);
System.out.println("Heap sort: " + (System.nanoTime()-start)/1_000_000 + "ms");
}
static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n/2-1; i >= 0; i--) siftDown(arr, n, i);
for (int i = n-1; i > 0; i--) {
int t=arr[0]; arr[0]=arr[i]; arr[i]=t;
siftDown(arr, i, 0);
}
}
static void siftDown(int[] a, int sz, int p) {
int lg=p, l=2*p+1, r=2*p+2;
if(l<sz&&a[l]>a[lg])lg=l; if(r<sz&&a[r]>a[lg])lg=r;
if(lg!=p){int t=a[p];a[p]=a[lg];a[lg]=t;siftDown(a,sz,lg);}
}
}
Arrays.sort: 80ms
Heap sort: 200ms
What is the time and space complexity?
| Phase | Time | Reason |
|---|---|---|
| Build heap | O(n) | Most nodes near bottom |
| Sort down | O(n log n) | n extractions at log n each |
| Total | O(n log n) | All cases |
| Space | O(1) | In-place |
How is the heap structure used beyond sorting?
The heap is far more commonly used as a priority queue than for sorting. Java's PriorityQueue is a min-heap that supports O(log n) insert and extract-min. It is used for Dijkstra's algorithm, merge-K-sorted-lists, and scheduling tasks by priority.
package com.bank.sort;
import java.util.PriorityQueue;
public class PriorityQueueUsage {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(50000);
pq.offer(10000);
pq.offer(30000);
while (!pq.isEmpty()) {
System.out.println("Poll: " + pq.poll());
}
}
}
Poll: 10000
Poll: 30000
Poll: 50000
What are common mistakes?
The most common mistake is an off-by-one error in the child index bounds check, allowing an access beyond the active heap size. Another mistake is forgetting that sift-down must be recursive (or iterative) until the node reaches its final position.
Visual Overview
Binary Max-Heap in Array:
Index: 0 1 2 3 4 5
Value: [80] [50] [70] [20] [40] [10]
80
/ \
50 70
/ \ /
20 40 10
Sort-Down Phase:
Step 1: Swap 80 with last (10), sift down 10
[10, 50, 70, 20, 40 | 80] -> sift 10 -> [70, 50, 10, 20, 40 | 80]
Step 2: Swap 70 with last active (40), sift down 40
[40, 50, 10, 20 | 70, 80] -> sift 40 -> [50, 40, 10, 20 | 70, 80]
... continue until sorted:
[10, 20, 40, 50, 70, 80]
Key Takeaway
Heap sort is a comparison-based, in-place sort built on a binary max-heap stored directly in the array. It has two phases: build the max-heap in O(n) time, then repeatedly extract the maximum by swapping it to the end and sifting the new root down, which takes O(n log n) total. This O(n log n) holds in the best, average, and worst case with O(1) extra space.
The sift-down procedure is the core logic: it takes a node that may violate the heap property, compares it against its larger child, and swaps it down until the property is restored. Building the heap by sifting down from the last parent is O(n) because most nodes are near the bottom with short sift distances.
In a banking system at the National Bank of India, heap sort is reserved for memory-constrained nodes that cannot afford merge sort's O(n) buffer and cannot risk quick sort's quadratic worst case. Its cache-unfriendly access pattern makes it slower than quick sort in practice, which is why it is not the default.
The heap structure itself is more commonly used as a priority queue. Java's PriorityQueue is a min-heap powering Dijkstra's algorithm, merge-K-sorted-lists, and task scheduling, which is where heaps really earn their keep in production.
Remember one sentence: heap sort builds a max-heap in-place, extracts the maximum repeatedly, and guarantees O(n log n) with O(1) space, but cache-unfriendly access keeps it niche compared to quick sort.
---