Build Heap from Array Heapify in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the index of the last non-leaf node in the heap array.

DSA Python

last_non_leaf = len(arr) [1] 2 - 1

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or - instead of integer division

Using normal division which returns float

Using multiplication instead of division

The last non-leaf node in a heap array is at index len(arr) // 2 - 1. This is because nodes after this index are leaves.

2fill in blank

medium

Complete the code to swap elements at indices i and j in the array.

DSA Python

arr[[1]], arr[j] = arr[j], arr[[1]]

Drag options to blanks, or click blank then click option'

Ai

Bj

C0

Dlen(arr)

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with wrong indices

Using j twice instead of i and j

Using 0 or len(arr) as index incorrectly

To swap elements at indices i and j, use arr[i], arr[j] = arr[j], arr[i].

3fill in blank

hard

Fix the error in the condition to check if the left child exists in the heapify function.

DSA Python

if left [1] len(arr):

Drag options to blanks, or click blank then click option'

A<

B>=

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or >= which is incorrect

Using <= which allows out of range index

Confusing the comparison direction

To check if the left child index is within the array bounds, use left < len(arr).

4fill in blank

hard

Fill both blanks to complete the heapify function's recursive call and comparison for the right child.

DSA Python

if right [1] len(arr) and arr[right] [2] arr[largest]:
    largest = right
if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, largest)

Drag options to blanks, or click blank then click option'

A<

B>

C<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators

Not checking index bounds before accessing array

Mixing up < and <= for index check

The right child index must be less than the array length (right < len(arr)) and its value greater than the current largest (arr[right] > arr[largest]) to update largest.

5fill in blank

hard

Fill all three blanks to complete the build_heap function that calls heapify from the last non-leaf node up to the root.

DSA Python

for i in range(len(arr) // 2 - 1, [1], [2]):
    [3](arr, i)

Drag options to blanks, or click blank then click option'

Aheapify

B-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong stop index in range

Using positive step instead of negative

Not calling heapify inside the loop

The loop runs from the last non-leaf node index down to 0 (inclusive), so range(len(arr)//2 - 1, -1, -1). Inside the loop, call heapify(arr, i).

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