Heap sort algorithm in Data Structures Theory - Time & Space Complexity

Time Complexity: Heap sort algorithm

O(n log n)

Understanding Time Complexity

Heap sort is a popular sorting method that uses a special tree structure called a heap.

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

Scenario Under Consideration

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

function heapSort(array) {
  buildMaxHeap(array);
  for (let end = array.length - 1; end > 0; end--) {
    swap(array, 0, end);
    siftDown(array, 0, end - 1);
  }
}

function buildMaxHeap(array) {
  let start = Math.floor((array.length - 2) / 2);
  while (start >= 0) {
    siftDown(array, start, array.length - 1);
    start--;
  }
}

function siftDown(array, start, end) {
  let root = start;
  while (root * 2 + 1 <= end) {
    let child = root * 2 + 1;
    let swapIdx = root;
    if (array[swapIdx] < array[child]) swapIdx = child;
    if (child + 1 <= end && array[swapIdx] < array[child + 1]) swapIdx = child + 1;
    if (swapIdx === root) return;
    swap(array, root, swapIdx);
    root = swapIdx;
  }
}
    

This code sorts an array by first building a max heap, then repeatedly swapping the largest element to the end and fixing the heap.

Identify Repeating Operations

• Primary operation: The siftDown process that moves elements down the heap to maintain order.
• How many times: It runs once for each non-leaf node during heap building, and once for each element during sorting.

How Execution Grows With Input

As the list size grows, the number of operations grows in a way that is a bit more than linear but less than quadratic.

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

Pattern observation: The operations grow roughly proportional to n times the logarithm of n, meaning the work increases moderately as input grows.

Final Time Complexity

Time Complexity: O(n log n)

This means if you double the size of the list, the time to sort grows a bit more than double, but much less than square.

Common Mistake

[X] Wrong: "Heap sort is as slow as bubble sort because both swap elements repeatedly."

[OK] Correct: Heap sort smartly organizes data in a heap to reduce unnecessary comparisons, making it much faster than simple swapping methods like bubble sort.

Interview Connect

Understanding heap sort's time complexity helps you explain efficient sorting methods clearly, a skill useful in many coding discussions and real projects.

Self-Check

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