Build Heap from Array Heapify in DSA Python

Mental Model

We turn a messy list into a special tree where parents are bigger than children by fixing from bottom up.

Analogy: Imagine stacking boxes so bigger boxes are always below smaller ones. We start fixing from the bottom boxes up to the top to keep the stack stable.

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10     3
  /  \
 5    1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Convert the array into a max heap where every parent is bigger than its children

Step 1: Start heapify from last parent index (1), fix subtree rooted at index 1

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10     3
  /  \
 5    1 ↑

Why: We fix from bottom up to ensure children are heaps before parents

Step 2: Compare node 10 with children 5 and 1, no swap needed

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10     3
  /  \
 5    1

Why: Subtree rooted at index 1 is already a max heap

Step 3: Move to parent index 0, fix subtree rooted at index 0

Array: [4, 10, 3, 5, 1]
Heap tree:
       4 ↑
     /   \
   10     3
  /  \
 5    1

Why: Now fix the root to satisfy max heap property

Step 4: Compare 4 with children 10 and 3, swap 4 with 10

Array: [10, 4, 3, 5, 1]
Heap tree:
      10
     /   \
    4     3
  /  \
 5    1

Why: Parent must be bigger than children, so swap with largest child

Step 5: Fix subtree rooted at index 1 (where 4 moved), compare 4 with children 5 and 1, swap 4 with 5

Array: [10, 5, 3, 4, 1]
Heap tree:
      10
     /   \
    5     3
  /  \
 4    1

Why: Continue fixing down the tree to maintain heap property

Step 6: Fix subtree rooted at index 3 (where 4 moved), no children to compare, stop

Array: [10, 5, 3, 4, 1]
Heap tree:
      10
     /   \
    5     3
  /  \
 4    1

Why: Leaf node reached, heap property restored

Result:

Array: [10, 5, 3, 4, 1]
Heap tree:
      10 -> 5 -> 3 -> 4 -> 1
Max heap built

Annotated Code

DSA Python

class MaxHeap:
    def __init__(self, array):
        self.heap = array
        self.build_heap()

    def build_heap(self):
        # Start from last parent and heapify down to root
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self.heapify(i)

    def heapify(self, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        # Check if left child exists and is greater than current largest
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left

        # Check if right child exists and is greater than current largest
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        # If largest is not root, swap and continue heapifying
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.heapify(largest)

    def __str__(self):
        return ' -> '.join(map(str, self.heap)) + ' -> null'

# Driver code
array = [4, 10, 3, 5, 1]
max_heap = MaxHeap(array)
print(max_heap)

for i in range(len(self.heap) // 2 - 1, -1, -1):

start heapify from last parent node up to root

if left < len(self.heap) and self.heap[left] > self.heap[largest]:

check if left child is bigger than current largest

if right < len(self.heap) and self.heap[right] > self.heap[largest]:

check if right child is bigger than current largest

if largest != i:

if child is bigger than parent, swap and heapify down

self.heapify(largest)

continue fixing subtree after swap

Output

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

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) in worst case but overall sums to O(n)

Space: O(1) because heapify is done in place without extra space

vs Alternative: Naive approach inserting elements one by one into heap takes O(n log n), this bottom-up heapify is faster at O(n)

Edge Cases

empty array

build_heap does nothing, heap remains empty

DSA Python

for i in range(len(self.heap) // 2 - 1, -1, -1):

single element array

heapify called once on index 0 but no swaps needed; single element is already a valid heap

DSA Python

for i in range(len(self.heap) // 2 - 1, -1, -1):

all elements equal

no swaps needed, heap property already satisfied

DSA Python

if largest != i:

When to Use This Pattern

When you need to build a heap quickly from an unordered list, use bottom-up heapify starting from last parent to root to efficiently build the heap.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last parent causes incorrect heap
Fix: Start heapify from last parent index len(array)//2 - 1 down to 0

Mistake: Not recursively heapifying after swap misses fixing deeper subtree
Fix: Call heapify recursively on the swapped child's index

Summary

Builds a max heap from an unordered array by fixing subtrees from bottom up.

Use when you want to convert an array into a heap efficiently before heap operations.

Start heapify from last parent node down to root to ensure all subtrees satisfy heap property.

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