Heap Sort Algorithm in DSA Java - Time & Space Complexity

Time Complexity: Heap Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time to sort a list using Heap Sort changes as the list grows.

How does the number of steps grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

Identify Repeating Operations

• Primary operation: The heapify function which rearranges elements to maintain the heap property.
• How many times: Heapify is called once for each non-leaf node during building the heap (about n/2 times), and then called for each element removed from the heap (n-1 times), each call may recurse down the tree.

How Execution Grows With Input

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

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 a bit faster than linearly but much slower than quadratically, roughly 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 input size by the height of the heap.

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 that limits how far elements move, so it runs much faster than simple nested loops.

Interview Connect

Understanding Heap Sort's time complexity shows you can analyze efficient sorting methods, a key skill for many coding challenges and real-world tasks.

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 count the number of elements in the array

B. To store elements in sorted order permanently

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

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure where the parent node is either greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role in Heap Sort

   Heap Sort uses a max-heap to quickly find the largest element at the root, then removes it to build the sorted array.

3. Final Answer:

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

4. Quick Check:

   Heap = fast max/min retrieval [OK]

Hint: Heap always keeps largest or smallest element on top [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with a simple array
• Assuming heap counts elements

2. Which of the following is the correct way to build a max heap from an array in Java?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n);

C. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

D. for (int i = 0; i < n / 2; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify starting point

   Heapify must start from the last non-leaf node, which is at index n/2 - 1, moving upwards.

2. Step 2: Loop direction and range

   The loop runs backwards from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n); -> Option B

4. Quick Check:

   Build heap from last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

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: Build max heap from array

   Max heap of [4,10,3,5,1] is [10,5,3,4,1].

2. Step 2: Extract max and heapify repeatedly

   Remove 10, heapify remaining; then 5, then 4, then 3, then 1, resulting in sorted array [1,3,4,5,10].

3. Final Answer:

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

4. Quick Check:

   Heap Sort sorts ascending [OK]

Hint: Heap Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing max heap array with sorted array
• Forgetting to heapify after extraction
• Assuming heap sort outputs descending by default

4. Identify the error in this heapify method snippet for max heap in Java:

void heapify(int[] arr, int i, int n) {
  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) {
    int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
    heapify(arr, largest, n);
  }
}

medium

A. The swap logic is incorrect

B. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

C. The indices for left and right children are incorrect

D. The comparison for left child should be '>' instead of '<'

Solution

1. Step 1: Check comparison operators for max heap

   For max heap, parent should be greater than children, so we check if child > parent to update largest.

2. Step 2: Identify incorrect comparison

   The code uses 'arr[left] < arr[largest]' which is wrong; it should be 'arr[left] > arr[largest]'.

3. Final Answer:

   The comparison for left child should be '>' instead of '<' -> Option D

4. Quick Check:

   Max heap needs '>' comparison [OK]

Hint: Max heap compares child > parent [OK]

Common Mistakes:

• Using '<' instead of '>' for max heap
• Wrong recursive call index
• Incorrect child index calculation

5. Given an array with many duplicate elements, how does Heap Sort behave and what is the time complexity in the worst case?

hard

A. Heap Sort handles duplicates normally with O(n log n) worst-case time

B. Heap Sort fails with duplicates and runs in O(n^2)

C. Heap Sort sorts duplicates faster with O(n) time

D. Heap Sort requires extra space for duplicates, increasing complexity

Solution

1. Step 1: Understand duplicates in Heap Sort

   Heap Sort treats duplicates like any other elements; duplicates do not affect the heap property or sorting steps.

2. Step 2: Time complexity with duplicates

   Heap Sort always runs in O(n log n) time in worst case, regardless of duplicates.

3. Final Answer:

   Heap Sort handles duplicates normally with O(n log n) worst-case time -> Option A

4. Quick Check:

   Duplicates do not affect Heap Sort time [OK]

Hint: Duplicates don't change Heap Sort time complexity [OK]

Common Mistakes:

• Thinking duplicates cause slower sorting
• Assuming Heap Sort needs extra space for duplicates
• Confusing Heap Sort with unstable sorts