Heap Sort Algorithm in DSA Python - 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.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

This code builds a heap from the list and then sorts it by repeatedly moving the largest item to the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The heapify function, which rearranges parts of the list to maintain the heap property.
• How many times: It is called once for each non-leaf node during heap building (about n/2 times), and then once for each element during sorting (n-1 times), each call doing work proportional to the height of the heap (log n).

How Execution Grows With Input

As the list size grows, the number of operations grows roughly by n times log n.

Input Size (n)	Approx. Operations
10	About 10 x 3 = 30
100	About 100 x 7 = 700
1000	About 1000 x 10 = 10,000

Pattern observation: When input size increases 10 times, operations increase about 10 times multiplied by a small factor (log n), so it grows faster than linear but much slower than quadratic.

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, but it stays efficient even for large lists.

Common Mistake

[X] Wrong: "Heap Sort is as slow as simple sorting methods like Bubble Sort because it uses loops inside loops."

[OK] Correct: Heap Sort uses a smart tree structure that limits how many times it rearranges items, so it runs much faster than simple methods that check every pair repeatedly.

Interview Connect

Understanding Heap Sort's time complexity helps you explain efficient sorting and tree-based algorithms clearly, a valuable skill in many coding discussions.

Self-Check

"What if we used a simple array instead of a heap structure for sorting? How would the time complexity change?"

Practice

1. What is the main purpose of the heapify process in the Heap Sort Algorithm?

easy

A. To reverse the array elements

B. To swap the first and last elements of the array

C. To build a max-heap or min-heap from an unsorted array

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy the heap property, making the array a max-heap or min-heap.

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to prepare the array for sorting by ensuring the largest (or smallest) element is at the root.

3. Final Answer:

   To build a max-heap or min-heap from an unsorted array -> Option C

4. Quick Check:

   Heapify = build heap [OK]

Hint: Heapify builds the heap structure before sorting [OK]

Common Mistakes:

• Thinking heapify swaps elements randomly
• Confusing heapify with sorting step
• Assuming heapify counts elements

2. Which of the following is the correct way to call the heapify function in Python for an array arr of size n at index i?

easy

A. heapify(arr, n, i)

B. heapify(i, arr, n)

C. heapify(arr, i, n)

D. heapify(n, i, arr)

Solution

1. Step 1: Recall heapify function signature

   Heapify is usually defined as heapify(array, size, index) to adjust the heap at index.

2. Step 2: Match parameters order

   The correct order is array first, then size, then index to correctly access elements and heap size.

3. Final Answer:

   heapify(arr, n, i) -> Option A

4. Quick Check:

   heapify(array, size, index) = heapify(arr, n, i) [OK]

Hint: Remember: array, size, then index in heapify call [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. What will be the output of the following Python code snippet using heap sort?

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [4, 10, 3, 5, 1]
heapSort(arr)
print(arr)

medium

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

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

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

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

Solution

1. Step 1: Build max heap from array

   Heapify rearranges array to max heap: [10, 5, 3, 4, 1]

2. Step 2: Extract elements and heapify

   Swap root with last element and heapify repeatedly to sort ascending: final array is [1, 3, 4, 5, 10]

3. Final Answer:

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

4. Quick Check:

   Heap sort output = sorted array ascending [OK]

Hint: Heap sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Expecting max heap array as final output
• Confusing heapify step with final sort
• Ignoring the swap and heapify loop

4. Identify the error in the following heap sort code snippet:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l <= n and arr[l] > arr[largest]:
        largest = l
    if r <= n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

medium

A. The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n'

B. The swap operation is missing

C. The function should return a value

D. The indices l and r are calculated incorrectly

Solution

1. Step 1: Check index boundary conditions

   Array indices go from 0 to n-1, so conditions must be 'l < n' and 'r < n' to avoid index error.

2. Step 2: Identify impact of wrong condition

   Using 'l <= n' or 'r <= n' can cause index out of range error when l or r equals n.

3. Final Answer:

   The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n' -> Option A

4. Quick Check:

   Index check uses less than n, not less or equal [OK]

Hint: Array indices go up to n-1, use '< n' not '<= n' [OK]

Common Mistakes:

• Using <= instead of < for array bounds
• Forgetting to swap elements
• Expecting heapify to return a value

5. Given an array with duplicate elements [4, 10, 4, 5, 1], how does heap sort handle duplicates, and what will be the sorted output?

hard

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

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

C. [1, 4, 5, 10]

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

Solution

1. Step 1: Understand heap sort with duplicates

   Heap sort treats duplicates as normal values and sorts them in ascending order without removal.

2. Step 2: Sort the array including duplicates

   Sorting [4, 10, 4, 5, 1] results in [1, 4, 4, 5, 10], preserving duplicates in order.

3. Final Answer:

   [1, 4, 4, 5, 10] -> Option B

4. Quick Check:

   Heap sort keeps duplicates, sorts ascending [OK]

Hint: Heap sort keeps duplicates, sorts all elements [OK]

Common Mistakes:

• Assuming duplicates are removed
• Expecting unsorted output with duplicates
• Confusing duplicates with errors