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?"

Practice

1. What is the main purpose of the heap in the Heap Sort algorithm?

easy

A. To reverse the array elements

B. To store elements in sorted order permanently

C. To count the number of elements in the array

D. To efficiently find and remove the largest (or smallest) element

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure that allows quick access to the largest (max-heap) or smallest (min-heap) element.

2. Step 2: Role in Heap Sort

   Heap Sort uses the heap to repeatedly extract the largest element and place it at the end, sorting the array.

3. Final Answer:

   To efficiently find and remove the largest (or smallest) element -> Option D

4. Quick Check:

   Heap = fast max/min access [OK]

Hint: Heap helps quickly get max or min element [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with simple array storage
• Assuming heap reverses the array

2. Which of the following is the correct way to swap two elements arr[i] and arr[j] in JavaScript during Heap Sort?

easy

A. let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Understand JavaScript swap syntax

   JavaScript does not support tuple unpacking like Python, so swapping requires a temporary variable.

2. Step 2: Check each option

   let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable correctly. arr[i], arr[j] = arr[j], arr[i]; is Python syntax, swap(arr[i], arr[j]); is undefined function, arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly.

3. Final Answer:

   let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Use temp variable to swap in JS [OK]

Common Mistakes:

• Using Python-style tuple swap in JS
• Calling undefined swap function
• Overwriting values without temp variable

3. What will be the output array after applying Heap Sort on [4, 10, 3, 5, 1]?

medium

A. [1, 3, 4, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 4, 3, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Understand Heap Sort output

   Heap Sort sorts the array in ascending order by default.

2. Step 2: Sort the array

   Sorting [4, 10, 3, 5, 1] gives [1, 3, 4, 5, 10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option A

4. Quick Check:

   Sorted ascending = [1, 3, 4, 5, 10] [OK]

Hint: Heap Sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing heap structure with final sorted array
• Thinking output is descending by default
• Mixing up original and sorted arrays

4. Identify the error in this Heap Sort snippet:

function heapSort(arr) {
  let n = arr.length;
  for (let i = Math.floor(n / 2); i >= 0; i--) {
    heapify(arr, n, i);
  }
  for (let i = n - 1; i > 0; i--) {
    let temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

medium

A. Swapping elements is done incorrectly

B. The first for loop should start from Math.floor(n / 2) - 1

C. The second for loop should start from i = 0

D. heapify function is called with wrong parameters

Solution

1. Step 1: Check heap building loop

   The first loop builds the heap and should start from the last non-leaf node at index Math.floor(n / 2) - 1, not Math.floor(n / 2).

2. Step 2: Verify other parts

   The second loop and swapping are correct. heapify parameters are also correct.

3. Final Answer:

   The first for loop should start from Math.floor(n / 2) - 1 -> Option B

4. Quick Check:

   Heap build starts at last non-leaf node [OK]

Hint: Heap build starts at floor(n/2)-1 [OK]

Common Mistakes:

• Starting heap build loop at wrong index
• Incorrect swap logic
• Wrong heapify parameters

5. Given an array [12, 11, 13, 5, 6, 7], how many times will the heapify function be called during the entire Heap Sort process?

hard

A. 6 times

B. 10 times

C. 13 times

D. 15 times

Solution

1. Step 1: Count heapify calls during heap build

   Heap build calls heapify top-level from index floor(n/2)-1=2 down to 0 (3 top-level). For this array, heapify(6,0) recurses once to heapify(6,2), total 4 calls.

2. Step 2: Count heapify calls during sorting

   After building heap, heapify called top-level 5 times (i=5 to 1). Tracing: i=5:2 calls, i=4:2, i=3:2, i=2:2, i=1:1, total 9 calls.

3. Step 3: Total calls

   Total heapify calls = 4 (build) + 9 (sort) = 13.

4. Final Answer:

   13 times -> Option C

5. Quick Check:

   Heapify calls = build + sort + recursive calls = 13 [OK]

Hint: Count build + sort + recursive heapify calls =13 [OK]

Common Mistakes:

• Counting only build or only sort calls
• Ignoring recursive heapify calls
• Assuming heapify called once per element