Heap Sort
What is a Heap?
A heap is a complete binary tree stored as an array where:
- Max-Heap: every parent node is ≥ its children. Root = maximum element.
- Min-Heap: every parent node is ≤ its children. Root = minimum element.
For a node at index i (0-indexed): left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
What is Heap Sort?
Heap sort uses a max-heap to sort an array in-place. It has two phases:
- Build Max-Heap — rearrange the array into a max-heap: O(n)
- Extract Max repeatedly — swap root (max) with last element, reduce heap size, heapify: O(n log n)
| Case | Time | Space | Stable? |
|---|---|---|---|
| Best / Average / Worst | O(n log n) | O(1) | No |
import java.util.Arrays;
public class HeapSort {
// Heapify subtree rooted at index i, heap size = n
static void heapify(int[] arr, int n, int i) {
int largest = i; // assume root is largest
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
// Swap root with largest child
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest); // recursively heapify affected subtree
}
}
static void heapSort(int[] arr) {
int n = arr.length;
// Phase 1: Build max-heap (start from last non-leaf node)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Phase 2: Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root (max) to end
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
// Heapify the reduced heap
heapify(arr, i, 0);
}
}
// Priority Queue using max-heap
static class MaxHeap {
int[] heap;
int size;
MaxHeap(int capacity) { heap = new int[capacity]; size = 0; }
void insert(int val) {
heap[size] = val;
int i = size++;
// Bubble up
while (i > 0 && heap[(i-1)/2] < heap[i]) {
int temp = heap[i]; heap[i] = heap[(i-1)/2]; heap[(i-1)/2] = temp;
i = (i - 1) / 2;
}
}
int extractMax() {
int max = heap[0];
heap[0] = heap[--size];
heapify(heap, size, 0);
return max;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Before: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("After: " + Arrays.toString(arr));
// After: [5, 6, 7, 11, 12, 13]
MaxHeap pq = new MaxHeap(10);
pq.insert(3); pq.insert(1); pq.insert(4); pq.insert(1); pq.insert(5);
System.out.print("Max extractions: ");
while (pq.size > 0) System.out.print(pq.extractMax() + " ");
// 5 4 3 1 1
}
}
/*
* Heap Sort advantages:
* - O(n log n) guaranteed — no worst case like Quick Sort
* - O(1) space — in-place
*
* Disadvantages:
* - Not stable
* - Poor cache performance (jumps around in memory)
* - In practice, Quick Sort is faster due to cache locality
*/Heap Sort — Step-by-Step
For array [12, 11, 13, 5, 6, 7]:
- Phase 1 — Build Max-Heap: Start from last non-leaf (index n/2-1=2) and heapify down. Result:
[13, 11, 12, 5, 6, 7] - Phase 2 — Extract Max repeatedly:
- Swap arr[0]=13 with arr[5]=7 →
[7, 11, 12, 5, 6, | 13], heapify →[12, 11, 7, 5, 6, | 13] - Swap arr[0]=12 with arr[4]=6 →
[6, 11, 7, 5, | 12, 13], heapify →[11, 6, 7, 5, | 12, 13] - Continue until sorted:
[5, 6, 7, 11, 12, 13]✓
- Swap arr[0]=13 with arr[5]=7 →
Sorting Algorithms — Complete Comparison
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Simple, slow |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Min swaps |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Best for small/nearly sorted |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed, stable |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest in practice |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Guaranteed, in-place |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Only integers in range [0,k] |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Non-comparison sort |