Heap Sort Algorithm in DSA Python - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. You decide to use the Heap Sort algorithm, which uses a special tree structure called a heap to sort the numbers.Heap Sort is useful in many real-world cases like organizing tasks by priority or sorting large data sets quickly.

🎯 Goal: Build a Python program that sorts a list of numbers using the Heap Sort algorithm. You will create the list, set up helper functions, implement the sorting logic, and finally print the sorted list.

📋 What You'll Learn

Create a list called numbers with the exact values [12, 11, 13, 5, 6, 7]

Create a function called heapify that maintains the max heap property

Create a function called heap_sort that sorts the list using heapify

Print the sorted list after applying heap_sort

💡 Why This Matters

🌍 Real World

Heap Sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in priority queues, scheduling tasks, and managing resources efficiently.

💼 Career

Understanding Heap Sort helps in technical interviews and is useful for software engineers working on performance-critical applications and data processing.

1

Create the list of numbers

Create a list called numbers with these exact values: [12, 11, 13, 5, 6, 7]

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets to create a list and separate the numbers with commas.

2

Define the heapify function

Define a function called heapify that takes three parameters: arr, n, and i. This function should maintain the max heap property for the subtree rooted at index i in the list arr of size n. Use variables largest, left, and right inside the function.

DSA Python

numbers = [12, 11, 13, 5, 6, 7]
# Define the heapify function below
# Your code here

Hint

Remember to check if left and right children exist before comparing. Swap and call heapify recursively if needed.

3

Define the heap_sort function

Define a function called heap_sort that takes a list arr and sorts it using the heapify function. Use a variable n for the length of the list. First, build a max heap by calling heapify from the last non-leaf node to the root. Then, extract elements one by one from the heap and call heapify again to maintain the heap.

DSA Python

numbers = [12, 11, 13, 5, 6, 7]

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

    if left  arr[largest]:
        largest = left

    if right  arr[largest]:
        largest = right

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

# Define the heap_sort function below
# Your code here

Hint

Build the heap first, then swap the root with the last element and heapify the reduced heap repeatedly.

4

Print the sorted list

Call the heap_sort function with the numbers list, then print the numbers list to show the sorted result.

DSA Python

Hint

Call heap_sort(numbers) first, then print numbers to see the sorted list.

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