Build Heap from Array Heapify in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min-Heap after Build Heap from Array

What is the printed state of the min-heap after building it from the array [4, 10, 3, 5, 1] using heapify?

DSA Python

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

    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

def build_min_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

arr = [4, 10, 3, 5, 1]
build_min_heap(arr)
print(' -> '.join(map(str, arr)) + ' -> null')

A 1 -> 4 -> 3 -> 10 -> 5 -> null

B 1 -> 3 -> 4 -> 5 -> 10 -> null

C 1 -> 4 -> 3 -> 5 -> 10 -> null

D 3 -> 4 -> 1 -> 5 -> 10 -> null

💡 Hint

Start heapify from the last non-leaf node and move upwards.

The build_min_heap function heapifies the array from the last non-leaf node upwards. After heapify, the smallest element is at the root, and the array represents a min-heap.

The final heap array is [1, 4, 3, 5, 10], printed as '1 -> 4 -> 3 -> 5 -> 10 -> null'.

❓ Predict Output

intermediate

Max-Heap Array after Build Heap from Array

Given the array [2, 7, 6, 3, 9], what is the max-heap array after applying build heap using heapify?

DSA Python

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

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

arr = [2, 7, 6, 3, 9]
build_max_heap(arr)
print(' -> '.join(map(str, arr)) + ' -> null')

A 9 -> 7 -> 3 -> 6 -> 2 -> null

B 9 -> 3 -> 7 -> 2 -> 6 -> null

C 7 -> 9 -> 6 -> 3 -> 2 -> null

D 9 -> 7 -> 6 -> 3 -> 2 -> null

💡 Hint

Heapify from bottom non-leaf nodes to root for max-heap.

After building the max-heap, the largest element is at the root. The array becomes [9, 7, 6, 3, 2].

🔧 Debug

advanced

Identify the Error in Heapify Function

What error will occur when running this heapify function on array [3, 1, 6, 5, 2, 4]?

DSA Python

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

    if left <= n and arr[left] < arr[smallest]:
        smallest = left
    if right <= n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

arr = [3, 1, 0, 5, 2, 4]
heapify(arr, len(arr), 0)
print(arr)

A TypeError: unsupported operand type(s)

B IndexError: list index out of range

C No error, prints [1, 2, 4, 5, 3, 6]

D RecursionError: maximum recursion depth exceeded

💡 Hint

Check the boundary conditions for left and right child indices.

The condition uses 'left <= n' and 'right <= n', but valid indices are less than n. This causes an IndexError when accessing arr[n].

❓ Predict Output

advanced

Resulting Array after Partial Heapify

What is the array after calling heapify(arr, 6, 1) on arr = [9, 4, 7, 1, 3, 6] assuming a min-heap?

DSA Python

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

    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

arr = [9, 4, 7, 1, 3, 6]
heapify(arr, 6, 1)
print(' -> '.join(map(str, arr)) + ' -> null')

A 9 -> 1 -> 7 -> 4 -> 3 -> 6 -> null

B 9 -> 3 -> 7 -> 4 -> 1 -> 6 -> null

C 9 -> 3 -> 7 -> 1 -> 4 -> 6 -> null

D 9 -> 4 -> 7 -> 1 -> 3 -> 6 -> null

💡 Hint

Heapify swaps the node with the smallest child and continues down.

Starting at index 1 (value 4), left child is 3 (index 3), right child is 4 (index 4). The smallest is 1 at index 3, so swap 4 and 1.

Then heapify at index 3 (value 4) has no children smaller, so stop.

Final array: [9, 1, 7, 4, 3, 6]

🧠 Conceptual

expert

Number of Heapify Calls in Build Heap

For an array of size n, what is the time complexity of building a heap using the heapify method from the bottom up?

A O(n) because heapify is called fewer times on lower levels and total work sums to linear

B O(log n) because heapify is called only once at the root

C O(n^2) because heapify is called n times and each call can take up to n time

D O(n log n) because each heapify call takes log n time and is called n times

💡 Hint

Consider the height of nodes and how many nodes are at each height.

Although heapify can take O(log n) time, it is called on fewer nodes at higher depths. The total time sums to O(n).

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