Build Heap from Array Heapify in DSA Python - Execution Trace

Concept Flow - Build Heap from Array Heapify

Start with array

↓

Find last non-leaf node

↓

For each node from last non-leaf to root

↓

Apply heapify on node

↓

Heap property restored at node

↓

Move to previous node

↓

Repeat until root heapified

↓

Heap built successfully

Start from the last non-leaf node and move upwards, applying heapify to restore heap property at each node until the root is heapified.

Execution Sample

DSA Python

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

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)

This code builds a max heap from an unsorted array by applying heapify from the last non-leaf node up to the root.

Execution Table

Step	Operation	Node Index	Nodes in Array	Pointer Changes	Visual State
1	Start build_heap	-	[4, 10, 3, 5, 1]	-	4 -> 10 -> 3 -> 5 -> 1
2	Find last non-leaf node	-	-	-	Last non-leaf index = 1
3	Heapify at index 1	1	[4, 10, 3, 5, 1]	largest=1, left=3, right=4	4 -> 10 -> 3 -> 5 -> 1
4	Compare left child (5) with current (10)	1	-	largest=1 (no change)	No swap
5	Compare right child (1) with current (10)	1	-	largest=1 (no change)	No swap
6	Heapify at index 0	0	[4, 10, 3, 5, 1]	largest=0, left=1, right=2	4 -> 10 -> 3 -> 5 -> 1
7	Compare left child (10) with current (4)	0	-	largest=1	Swap needed
8	Compare right child (3) with largest (10)	0	-	largest=1 (no change)	Swap 4 and 10
9	Swap arr[0] and arr[1]	0 & 1	[10, 4, 3, 5, 1]	arr[0]<->arr[1]	10 -> 4 -> 3 -> 5 -> 1
10	Heapify at index 1	1	[10, 4, 3, 5, 1]	largest=1, left=3, right=4	10 -> 4 -> 3 -> 5 -> 1
11	Compare left child (5) with current (4)	1	-	largest=3	Swap needed
12	Compare right child (1) with largest (5)	1	-	largest=3 (no change)	Swap 4 and 5
13	Swap arr[1] and arr[3]	1 & 3	[10, 5, 3, 4, 1]	arr[1]<->arr[3]	10 -> 5 -> 3 -> 4 -> 1
14	Heapify at index 3	3	[10, 5, 3, 4, 1]	largest=3, left=7, right=8 (out of range)	No children, stop
15	Build heap complete	-	[10, 5, 3, 4, 1]	-	10 -> 5 -> 3 -> 4 -> 1

💡 All non-leaf nodes heapified, heap property restored for entire array

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 13	Final
arr	[4, 10, 3, 5, 1]	[4, 10, 3, 5, 1]	[4, 10, 3, 5, 1]	[10, 4, 3, 5, 1]	[10, 5, 3, 4, 1]	[10, 5, 3, 4, 1]
largest	0	1	0	1	3	-
left	1	3	1	3	7	-
right	2	4	2	4	8	-
i (heapify index)	-	1	0	0	1	-

Key Moments - 3 Insights

Why do we start heapify from the last non-leaf node and not from the root?

Because leaf nodes have no children, they already satisfy heap property. Starting from last non-leaf node ensures we fix subtrees bottom-up as shown in steps 2 and 3.

Why does heapify call itself recursively after a swap?

After swapping, the subtree rooted at the swapped child might violate heap property. Recursive call fixes this, as seen in steps 10 to 14.

Why do we compare both left and right children before swapping?

To find the largest among parent and children to maintain max heap property. This is shown in steps 4, 5, 7, and 8.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 9?

A [10, 5, 3, 4, 1]

B [4, 10, 3, 5, 1]

C [10, 4, 3, 5, 1]

D [4, 5, 3, 10, 1]

💡 Hint

Check the 'Visual State' column at step 9 in the execution_table.

At which step does the heapify process first swap elements?

A Step 4

B Step 8

C Step 12

D Step 14

💡 Hint

Look for the first 'Swap needed' and 'Swap arr[0] and arr[1]' in the execution_table.

If the initial array was already a max heap, how would the execution table change?

A No swaps would occur during heapify calls

B Heapify would not be called at all

C The array would be reversed

D Heapify would swap all elements

💡 Hint

Refer to steps where 'No swap' is noted in the execution_table.

Concept Snapshot

Build Heap from Array (Heapify):
- Start from last non-leaf node (n//2 -1) down to 0
- Apply heapify at each node
- Heapify compares node with children, swaps with largest child if needed
- Recursively heapify affected subtree
- Result: array satisfies max heap property
- Time complexity: O(n)

Full Transcript

To build a max heap from an array, we start from the last non-leaf node and move upwards to the root. At each node, we apply heapify which compares the node with its children and swaps with the largest child if needed. After swapping, heapify is called recursively on the affected child to maintain heap property. This process continues until the root is heapified, resulting in a max heap. The execution table shows each step, including comparisons, swaps, and the array state changes. Key points include starting from the last non-leaf node because leaves are already heaps, and recursive heapify calls after swaps to fix subtrees. The final array represents a valid max 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