Heap Sort

A binary heap is a complete binary tree that satisfies the heap property. It's commonly implemented as an array.

Heap Property

• Max-Heap: Parent ≥ children (largest at root)
• Min-Heap: Parent ≤ children (smallest at root)

Array Representation

Max-Heap:        10
               /    \
              7      8
             / \\    / \
            5   6  3   4

Array: [10, 7, 8, 5, 6, 3, 4]

Index relationships (0-based):
- Parent of i: (i-1)/2
- Left child of i: 2*i + 1
- Right child of i: 2*i + 2

Java Heap Implementation

public class MaxHeap {
    private int[] heap;
    private int size;
    
    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }
    
    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Heapify (Sift Down)

private void heapify(int i) {
    int largest = i;
    int left = leftChild(i);
    int right = rightChild(i);
    
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }
    
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(i, largest);
        heapify(largest);  // Recursively heapify affected subtree
    }
}

Insert Operation

public void insert(int value) {
    if (size == heap.length) {
        throw new RuntimeException("Heap is full");
    }
    
    // Place at end and sift up
    heap[size] = value;
    size++;
    siftUp(size - 1);
}

private void siftUp(int i) {
    while (i > 0 && heap[parent(i)] < heap[i]) {
        swap(parent(i), i);
        i = parent(i);
    }
}

Extract Max/Min

public int extractMax() {
    if (size == 0) {
        throw new RuntimeException("Heap is empty");
    }
    
    int max = heap[0];
    heap[0] = heap[size - 1];
    size--;
    heapify(0);
    
    return max;
}

Build Heap from Array

public void buildHeap(int[] arr) {
    heap = arr;
    size = arr.length;
    
    // Start from last non-leaf node
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

Complexity

Heap sort uses a max-heap to sort in ascending order:

1. Build max-heap from array
2. Extract max repeatedly, placing at end

Algorithm Steps

1. Build max-heap (largest element at root)
2. Swap root (max) with last element
3. Reduce heap size by 1
4. Heapify root to maintain heap property
5. Repeat until heap size is 1

Visual Example

Original: [4, 10, 3, 5, 1]

Build Max-Heap: [10, 5, 3, 4, 1]

Iteration 1:
Swap 10 and 1: [1, 5, 3, 4, 10]
Heapify: [5, 4, 3, 1, 10]

Iteration 2:
Swap 5 and 1: [1, 4, 3, 5, 10]
Heapify: [4, 1, 3, 5, 10]

Iteration 3:
Swap 4 and 3: [3, 1, 4, 5, 10]
Heapify: [3, 1, 4, 5, 10]

Iteration 4:
Swap 3 and 1: [1, 3, 4, 5, 10]
Heapify: [1, 3, 4, 5, 10]

Sorted: [1, 3, 4, 5, 10]

Java Implementation

public 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 one by one
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        swap(arr, 0, i);
        
        // Heapify reduced heap
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i;
    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(arr, i, largest);
        heapify(arr, n, largest);
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Complexity Analysis

Heap Sort vs Other Sorts

When to Use Heap Sort

Use when:

• Guaranteed O(n log n) needed
• O(1) space required
• Priority queue operations needed
• Online sorting (elements arrive one by one)

Avoid when:

• Stability required (use merge sort)
• Cache performance important (quicksort better)
• Nearly sorted data (insertion sort better)