Build Heap from Array Heapify in DSA Python - Build from Scratch

Build Heap from Array Heapify

📖 Scenario: Imagine you have a list of numbers representing tasks with different priorities. You want to organize them so the highest priority task is always easy to find. This organization is called a heap.

🎯 Goal: You will build a max heap from an unsorted list of numbers using the heapify process. This means rearranging the list so each parent number is bigger than its children.

📋 What You'll Learn

Create a list called arr with the exact numbers given

Create a variable n to store the length of arr

Write a function heapify(arr, n, i) that fixes the heap property at index i

Use a loop to build the heap from the bottom up

Print the final heap list arr

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and algorithms like heap sort.

💼 Career

Understanding heaps helps in software engineering roles that involve efficient data processing and algorithm design.

1

Create the initial array

Create a list called arr with these exact numbers: 4, 10, 3, 5, 1

DSA Python

# Create the list arr with the numbers 4, 10, 3, 5, 1
# Your code here

Hint

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

2

Set the length variable

Create a variable called n and set it to the length of the list arr using len(arr)

DSA Python

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

Hint

Use the len() function to find the number of items in a list.

3

Write the heapify function

Write a function called heapify(arr, n, i) that does the following:
1. Sets largest to i
2. Finds left child index 2 * i + 1 and right child index 2 * i + 2
3. If left child is within n and bigger than arr[largest], update largest
4. If right child is within n and bigger than arr[largest], update largest
5. If largest is not i, swap arr[i] and arr[largest] and call heapify(arr, n, largest) again

DSA Python

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

Hint

Remember to check if child indexes are inside the list before comparing values.

4

Build the heap and print the result

Use a for loop with variable i starting from n // 2 - 1 down to 0 (inclusive) to call heapify(arr, n, i) for each i. Then print the list arr.

DSA Python

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)

# Build the heap using a for loop
# Print the final heap list
# Your code here

Hint

Start from the last parent node and move upwards to the root to fix the heap.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To rearrange the array elements to satisfy the heap property

B. To sort the array in ascending order

C. To reverse the array elements

D. To remove duplicate elements from the array

Solution

1. Step 1: Understand heap property

   The heap property requires each parent node to be greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements to ensure this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option A

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree to maintain heap order [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with reversing array
• Assuming heapify removes duplicates

2. Which of the following is the correct Python syntax to call the heapify function from the heapq module on a list named arr?

easy

A. arr.heapify()

B. heapify.heapq(arr)

C. heapq.heapify(arr)

D. heapq.heapify = arr

Solution

1. Step 1: Identify module and function

   The heapq module provides the heapify function to convert a list into a heap.

2. Step 2: Correct function call syntax

   The correct syntax is heapq.heapify(arr) after importing heapq.

3. Final Answer:

   heapq.heapify(arr) -> Option C

4. Quick Check:

   heapq.heapify(list) is correct call [OK]

Hint: Call heapify as heapq.heapify(list) after import [OK]

Common Mistakes:

• Using wrong order like heapify.heapq(arr)
• Calling heapify as a method on list
• Assigning heapify function instead of calling

3. What will be the output of the following Python code?

import heapq
arr = [3, 1, 6, 5, 2, 4]
heapq.heapify(arr)
print(arr)

medium

A. [6, 5, 4, 3, 2, 1]

B. [1, 2, 4, 5, 3, 6]

C. [1, 3, 2, 5, 6, 4]

D. [3, 1, 6, 5, 2, 4]

Solution

1. Step 1: Understand heapq.heapify behavior

   heapq.heapify converts list into a min-heap, smallest element at root (index 0).

2. Step 2: Apply heapify on given list

   After heapify, the list becomes [1, 2, 4, 5, 3, 6], which satisfies min-heap property.

3. Final Answer:

   [1, 2, 4, 5, 3, 6] -> Option B

4. Quick Check:

   heapify(min-heap) = [1, 2, 4, 5, 3, 6] [OK]

Hint: heapq.heapify creates min-heap, smallest first [OK]

Common Mistakes:

• Expecting sorted list instead of heap order
• Confusing max-heap with min-heap output
• Assuming original list order remains

4. The following code attempts to build a heap from an array but does not produce the correct heap. What is the error?

def build_heap(arr):
    n = len(arr)
    for i in range(n):
        heapify(arr, i, n)

def heapify(arr, i, n):
    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, largest, n)

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

medium

A. The loop should run from n//2 - 1 down to 0, not from 0 to n

B. The heapify function should use min-heap logic instead of max-heap

C. The swap inside heapify is missing

D. The array length n is calculated incorrectly

Solution

1. Step 1: Analyze build_heap loop range

   Heap building requires heapify calls from last non-leaf node down to root, i.e., from n//2 - 1 down to 0.

2. Step 2: Identify incorrect loop direction

   The code loops from 0 to n, which is incorrect and misses proper heapify order.

3. Final Answer:

   The loop should run from n//2 - 1 down to 0, not from 0 to n -> Option A

4. Quick Check:

   Build heap loop must go bottom-up [OK]

Hint: Build heap bottom-up from last parent to root [OK]

Common Mistakes:

• Looping top-down instead of bottom-up
• Confusing min-heap and max-heap logic
• Forgetting to swap elements in heapify

5. Given an array arr = [9, 4, 7, 1, -2, 6, 5], you want to build a max-heap using the heapify method. Which sequence of indices should you call heapify on to build the heap correctly?

hard

A. From index 0 to len(arr)-1 in ascending order

B. Only on index 0

C. From index len(arr)-1 down to 0 in descending order

D. From index len(arr)//2 - 1 down to 0 in descending order

Solution

1. Step 1: Identify last non-leaf node

   For array length 7, last non-leaf node is at index 7//2 - 1 = 2.

2. Step 2: Correct heapify call order

   Heapify must be called from index 2 down to 0 to ensure all subtrees satisfy max-heap property.

3. Final Answer:

   From index len(arr)//2 - 1 down to 0 in descending order -> Option D

4. Quick Check:

   Heapify bottom-up from last parent to root [OK]

Hint: Start heapify from last parent index down to root [OK]

Common Mistakes:

• Calling heapify in ascending order
• Calling heapify only on root
• Calling heapify on all indices including leaves