Heap Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Heap Sort Algorithm

O(n log n)

Understanding Time Complexity

Heap Sort is a way to sort items by using a special tree structure called a heap.

We want to know how the time it takes to sort grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function heapSort(arr) {
  let n = arr.length;

  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Extract elements from heap
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

function heapify(arr, size, root) {
  let largest = root;
  let left = 2 * root + 1;
  let right = 2 * root + 2;

  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}
    

This code sorts an array by first building a max heap, then repeatedly removing the largest item and fixing the heap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The heapify function, which rearranges parts of the array to maintain the heap property.
• How many times: Called once for each non-leaf node during heap building, and once for each element during sorting, with recursion inside.

How Execution Grows With Input

As the list size grows, the number of operations grows a bit more than linearly but less than quadratically.

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 roughly proportional to n times log n, meaning if input size doubles, operations grow a bit more than double.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit more than linearly as the list gets bigger, making heap sort efficient for large lists.

Common Mistake

[X] Wrong: "Heap sort is as slow as bubble sort because both use loops inside loops."

[OK] Correct: Heap sort uses a smart tree structure to reduce repeated work, so it grows much slower than bubble sort, which compares every pair.

Interview Connect

Understanding heap sort's time complexity shows you can analyze how smart data structures help algorithms run faster, a key skill in coding interviews.

Self-Check

"What if we used a min heap instead of a max heap? How would the time complexity change?"