Heap sort algorithm in Data Structures Theory - Mini Project: Build & Apply

Heap sort algorithm

📖 Scenario: You have a list of numbers that you want to sort in ascending order. You will use the heap sort algorithm, which organizes the numbers into a special tree structure called a heap to help sort them efficiently.

🎯 Goal: Build the heap sort algorithm step-by-step to sort a list of numbers in ascending order using a max heap.

📋 What You'll Learn

Create a list of unsorted numbers

Set up a helper function to maintain the heap property

Build a max heap from the list

Perform the heap sort to get the sorted list

💡 Why This Matters

🌍 Real World

Heap sort is used in computer systems and applications where efficient sorting is needed, such as priority queues and scheduling tasks.

💼 Career

Understanding heap sort helps in software development and data engineering roles where sorting large datasets efficiently is important.

1

Create the list of numbers

Create a list called numbers with these exact values: [4, 10, 3, 5, 1].

Data Structures Theory

# Create the list called numbers with the values [4, 10, 3, 5, 1]
numbers = []  # Your code here

Need a 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 will help maintain the max heap property by comparing parent and child nodes.

Data Structures Theory

numbers = [4, 10, 3, 5, 1]
# Define the heapify function with parameters arr, n, and i
def heapify(arr, n, i):
    # Your code here

Need a hint?

Use the formulas left = 2 * i + 1 and right = 2 * i + 2 to find child indices. Swap if children are larger than the parent.

3

Build the max heap

Use a for loop with variable i starting from len(numbers) // 2 - 1 down to 0 (inclusive) to call heapify(numbers, len(numbers), i) and build the max heap.

Data Structures Theory

numbers = [4, 10, 3, 5, 1]
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)

# Build the max heap using a for loop
# Your code here

Need a hint?

Start from the middle of the list and move backwards to the first element to build the heap.

4

Perform heap sort

Use a for loop with variable i starting from len(numbers) - 1 down to 1 (inclusive). Inside the loop, swap numbers[0] and numbers[i], then call heapify(numbers, i, 0) to maintain the heap. This completes the heap sort.

Data Structures Theory

numbers = [4, 10, 3, 5, 1]
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)

for i in range(len(numbers) // 2 - 1, -1, -1):
    heapify(numbers, len(numbers), i)

# Perform heap sort using a for loop
# Your code here

Need a hint?

Swap the first and last elements, then reduce the heap size by one and heapify again.