Heapify operation in Data Structures Theory - Mini Project: Build & Apply

Heapify Operation

📖 Scenario: You are learning about heaps, a special kind of tree used in many computer applications like priority queues and sorting. The heapify operation helps organize an unordered list into a heap structure.

🎯 Goal: Build a step-by-step understanding of the heapify operation by creating a list of numbers, setting a starting index, applying the heapify logic, and completing the process to maintain the heap property.

📋 What You'll Learn

Create a list called arr with the exact values [4, 10, 3, 5, 1]

Create a variable called n that stores the length of arr

Write a function called heapify that takes arr, n, and an index i and applies the heapify operation

Call the heapify function with arr, n, and i = 1 to adjust the heap

💡 Why This Matters

🌍 Real World

Heapify is used in priority queues, scheduling tasks, and sorting algorithms like heap sort.

💼 Career

Understanding heapify helps in software development roles involving data structures, algorithms, and performance optimization.

1

Create the initial list

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

Data Structures Theory

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

Need a hint?

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

2

Set the length variable

Create a variable called n that stores the length of the list arr using the len() function

Data Structures Theory

arr = [4, 10, 3, 5, 1]
# Create variable n to store the length of arr
# Your code here

Need a hint?

Use len(arr) to get the number of elements in the list.

3

Write the heapify function

Write a function called heapify that takes parameters arr, n, and i. Inside, find the largest among i, its left child 2*i + 1, and right child 2*i + 2. If the largest is not i, swap and recursively call heapify on the largest index.

Data Structures Theory

arr = [4, 10, 3, 5, 1]
n = len(arr)
# Define the heapify function below
# Your code here

Need a hint?

Remember to check if left and right child indices are within the list length before comparing values.

4

Apply heapify to the list

Call the heapify function with the list arr, its length n, and the index i = 1 to adjust the heap starting at that index

Data Structures Theory

arr = [4, 10, 3, 5, 1]
n = len(arr)

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)

# Call heapify with i = 1
# Your code here

Need a hint?

Use the function name heapify and pass the variables arr, n, and 1 as arguments.