DSA — Heap Sort

What is Heap Sort?

Uses a binary heap to sort elements by building a max heap and extracting maximum.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Characteristics

• Not stable
• In-place
• Consistent performance
• Good for priority queues

Mini Practice

1. Implement heap sort
2. Build max heap
3. Sort in descending order
4. Compare with quick sort

Up Next

Continue with Counting Sort — non-comparison sort.