Heap Sort Algorithm in DSA Go - 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 list size grows.

How does the number of steps increase when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

func heapify(arr []int, n, i int) {
  largest := i
  left := 2*i + 1
  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 {
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  }
}
    

This code builds a max heap from the array, then repeatedly swaps the largest element to the end and fixes the heap.

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: The first loop calls heapify about n/2 times; the second loop calls heapify n-1 times, each potentially recursing down the heap.

How Execution Grows With Input

As the list size grows, the number of operations grows more than just a simple multiple.

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

Pattern observation: The operations grow roughly proportional to n times log n, meaning it grows faster than n but slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means if the list doubles in size, the time to sort grows a bit more than double, but much less than four times.

Common Mistake

[X] Wrong: "Heap Sort is as slow as bubble sort because it uses loops inside loops."

[OK] Correct: Heap Sort uses a smart tree structure to reduce repeated work, so it sorts much faster than simple nested loops.

Interview Connect

Understanding Heap Sort's time complexity shows you can analyze efficient sorting methods, a key skill in many coding challenges.

Self-Check

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