Heap Sort Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Heap Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by heap sort changes as the input size grows.

Specifically, how the number of steps increases when sorting more items.

Scenario Under Consideration

Analyze the time complexity of the following heap sort code snippet.

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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}
    

This code builds a max heap from the array, then repeatedly extracts the largest element to sort the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The heapify function called multiple times to maintain the heap property.
• How many times: First, heapify is called for each non-leaf node once (about n/2 times). Then, it is called once per element during sorting (n times), each possibly recursing down the tree.

How Execution Grows With Input

As the input size grows, the number of operations grows roughly proportional to n times the height of the heap.

Input Size (n)	Approx. Operations
10	About 30 to 40 heapify steps
100	About 700 to 800 heapify steps
1000	About 10,000 to 12,000 heapify steps

Pattern observation: Operations grow a bit faster than linearly but much slower than quadratically, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a little more than linearly, multiplying the number of items by the height of the heap.

Common Mistake

[X] Wrong: "Heap sort is just like bubble sort and takes O(n²) time because of nested loops."

[OK] Correct: Heap sort uses a tree structure and heapify steps that take logarithmic time, so it is much faster than simple nested loops.

Interview Connect

Understanding heap sort's time complexity shows you can analyze algorithms that combine loops and recursion, a key skill in many coding challenges.

Self-Check

"What if we changed the heap from a max heap to a min heap? How would the time complexity change?"