Step 4 of 7

57% Complete

Heap Sort

Learn the guaranteed O(n log n) in-place sorting algorithm: Heap Sort

What is Heap Sort?

Heap Sort is an efficient sorting algorithm that uses a heap data structure to sort elements. It guarantees O(n log n) time complexity while using O(1) extra space, making it both time and space efficient. Unlike Quick Sort, Heap Sort provides consistent performance in all cases.

Heap Sort is particularly useful when you need guaranteed O(n log n) performance and want to avoid the worst-case O(n²) of Quick Sort.

How Heap Sort Works

Algorithm Steps

Build Phase: Build a max heap from the array
Extraction Phase: Repeatedly extract the maximum element
Place extracted element at end of sorted portion
Restore heap property with remaining elements
Repeat until heap is empty

Heap Sort - Visual Example

// Initial array: [64, 34, 25, 12, 22, 11, 90]
 
// Step 1: Build max heap
// After heapify:
//         90
//        /  \
//       34   64
//      / \  / \
//     12 22 11 25
 
// Step 2: Extract max (90), place at end, reheapify
// Heap: [64, 34, 25, 12, 22, 11]  Sorted: [90]
 
// Step 3: Extract max (64), place at end, reheapify
// Heap: [34, 25, 22, 12, 11]  Sorted: [64, 90]
 
// Continue until sorted: [11, 12, 22, 25, 34, 64, 90]

Understanding Heaps

Max Heap Property

In a max heap, every parent node is greater than or equal to its children. The root contains the maximum element.

Array representation:

Node at index i has left child at 2i + 1
Node at index i has right child at 2i + 2
Node at index i has parent at (i - 1) / 2

Implementation

Heap Sort Implementation

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 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;
            
            // Restore heap property for reduced heap
            heapify(arr, i, 0);
        }
    }
    
    // Heapify subtree rooted at index i
    // n is heap size
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;  // Assume current is largest
        int left = 2 * i + 1;    // Left child
        int right = 2 * i + 2;   // Right child
        
        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // If right child is larger than current largest
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // If largest is not root, swap and continue heapifying
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            
            heapify(arr, n, largest);
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        heapSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Output: [11, 12, 22, 25, 34, 64, 90]
    }
}

Detailed Heapify Example

How Heapify Restores Heap Property

// Heapify process on array [64, 34, 25, 12, 22, 11, 90]
//
// Step 1: Start from index n/2 - 1 = 2 (element 25)
//         No children to compare, no change
//
// Step 2: Index 1 (element 34)
//         34 < 22 (right child)? No change
//
// Step 3: Index 0 (element 64)
//         64 < 90 (right child)? Yes, swap
//         Result: [90, 34, 25, 12, 22, 11, 64]
//         Recursively heapify at index 2 (now 64)
//         64 > 11, no change
//
// Max heap built: [90, 34, 25, 12, 22, 11, 64]

Time & Space Complexity

Time Complexity

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Space Complexity

O(1) - In-place sorting

No extra data structures needed

Why O(n log n)?

Building the heap takes O(n) time. Extracting n elements and heapifying takes O(n log n) because each extraction is O(log n) and we do it n times.

Unlike Quick Sort, this complexity is guaranteed in all cases.

Characteristics

✗ Not stable: May change order of equal elements

✓ In-place: Requires O(1) extra space

✓ Guaranteed: Always O(n log n)

✗ Not adaptive: No advantage on sorted data

When to Use Heap Sort

Good for:

When guaranteed O(n log n) performance is needed
Memory-constrained systems (O(1) space)
When avoiding worst-case O(n²) of Quick Sort
Finding k largest/smallest elements

Avoid for:

When stability is required
When cache locality matters (poor locality)
When average-case performance matters most (slower than Quick Sort)

Heap Sort vs Other O(n log n) Sorts

Aspect	Heap Sort	Quick Sort	Merge Sort
Time (worst)	O(n log n)	O(n²)	O(n log n)
Space	O(1)	O(log n)	O(n)
Stable	No	No	Yes
Cache friendly	No	Yes	No
Practical speed	Slower	Fastest	Medium

Key Takeaways

Heap Sort uses max heap to efficiently sort elements
Guarantees O(n log n) time - better worst case than Quick Sort
O(1) space makes it ideal for memory-constrained systems
Not stable, so equal elements may be reordered
Slower in practice than Quick Sort due to poor cache locality
Useful when guaranteed performance is more important than average speed
Foundation for priority queue implementations