Heap Sort Algorithm in DSA Python

Mental Model

Heap sort organizes data into a special tree shape called a heap, then repeatedly removes the largest item to sort the list.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. You keep taking the biggest book off the pile and placing it in order, making the pile smaller each time.

Array: [4, 10, 3, 5, 1]
Heap view:
        10
       /  \
      5    3
     / \
    4   1

Dry Run Walkthrough

Input: list: [4, 10, 3, 5, 1]

Goal: Sort the list in ascending order using heap sort

Step 1: Build max heap from the array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root (index 0)

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move largest element to its correct sorted position at the end

Step 3: Heapify root to restore max heap for first 4 elements

[5, 4, 3, 1, 10]

Why: Fix heap after removing largest element to prepare for next extraction

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place next largest element in correct position

Step 5: Heapify root for first 3 elements

[4, 1, 3, 5, 10]

Why: Restore max heap property for remaining unsorted elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in correct position

Step 7: Heapify root for first 2 elements

[3, 1, 4, 5, 10]

Why: Restore max heap property for remaining unsorted elements

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in correct position

Step 9: Heapify root for first element (only one element left, no change)

[1, 3, 4, 5, 10]

Why: Heap of size 1 is already sorted

Result:

Sorted array: [1, 3, 4, 5, 10]

Annotated Code

DSA Python

class HeapSort:
    def heapify(self, arr, n, i):
        largest = i  # Initialize largest as root
        left = 2 * i + 1  # left child index
        right = 2 * i + 2  # right child index

        # Check if left child exists and is greater than root
        if left < n and arr[left] > arr[largest]:
            largest = left

        # Check if right child exists and is greater than current largest
        if right < n and arr[right] > arr[largest]:
            largest = right

        # Change root if needed
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]  # swap
            self.heapify(arr, n, largest)  # Heapify the affected subtree

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

        # Build max heap
        for i in range(n // 2 - 1, -1, -1):
            self.heapify(arr, n, i)

        # Extract elements one by one
        for i in range(n - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]  # swap
            self.heapify(arr, i, 0)


if __name__ == '__main__':
    arr = [4, 10, 3, 5, 1]
    sorter = HeapSort()
    sorter.heap_sort(arr)
    print(arr)

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

Check if left child is larger than current largest

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

Check if right child is larger than current largest

if largest != i:

If root is not largest, swap and heapify subtree

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

Build max heap starting from last non-leaf node

for i in range(n - 1, 0, -1):

Extract max element and heapify reduced heap

Output

[1, 3, 4, 5, 10]

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n elements is extracted with O(log n) heapify operations

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorting like bubble sort O(n^2), heap sort is much faster for large data due to efficient heap structure

Edge Cases

Empty array

No operations happen, output remains empty

DSA Python

n = len(arr)

Array with one element

Heapify and sorting steps do nothing, array stays the same

DSA Python

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

Array with all equal elements

Heapify swaps do not change order, output same as input

DSA Python

if arr[left] > arr[largest]

When to Use This Pattern

When you need to sort data efficiently in place and can use a tree-like structure, heap sort is a good choice because it uses a heap to repeatedly extract the largest element.

Common Mistakes

Mistake: Not building the max heap before sorting
Fix: Add the initial heap building loop before extraction

Mistake: Not reducing heap size after swapping root with last element
Fix: Pass the reduced heap size to heapify after each extraction

Mistake: Incorrect child index calculations
Fix: Use left = 2*i + 1 and right = 2*i + 2 for zero-based arrays

Summary

Heap sort sorts an array by building a max heap and repeatedly extracting the largest element.

Use heap sort when you want an in-place, efficient sorting algorithm with O(n log n) time.

The key insight is to maintain the heap property so the largest element is always at the root for easy extraction.

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