Build Heap from Array Heapify in DSA Go

Mental Model

We turn an unordered list into a heap by fixing each subtree from the bottom up, ensuring the heap property holds everywhere.

Analogy: Imagine organizing a pyramid of boxes where each box must be heavier than the boxes above it. You start fixing from the bottom rows up to the top, swapping boxes to keep the pyramid stable.

Array: [4, 10, 3, 5, 1]
Index:  0   1   2   3   4
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 each parent is greater than its children

Step 1: Start heapify at index 1 (value 10), check children at indices 3 and 4

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

Why: We start from the last non-leaf node to fix subtrees bottom-up

Step 2: Compare 10 with children 5 and 1, no swap needed as 10 is largest

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

Why: Subtree rooted at index 1 already satisfies max heap property

Step 3: Heapify at index 0 (value 4), compare with children 10 and 3

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

Why: Fix the root subtree to maintain heap property

Step 4: Swap 4 with largest child 10 at index 1

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

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

Step 5: Heapify at index 1 (value 4), compare with children 5 and 1

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

Why: After swap, fix subtree rooted at index 1

Step 6: Swap 4 with largest child 5 at index 3

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

Why: Maintain max heap property by swapping with largest child

Step 7: Heapify at index 3 (value 4), no children to compare, stop

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

Why: Leaf node reached, heapify complete

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

// Heapify fixes the subtree rooted at index i in array arr of size n
func heapify(arr []int, n int, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    // If left child exists and is greater than root
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // If right child exists and is greater than current largest
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // If largest is not root
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i] // swap
        heapify(arr, n, largest) // recursively heapify affected subtree
    }
}

// buildHeap converts array into a max heap
func buildHeap(arr []int) {
    n := len(arr)
    // Start from last non-leaf node and heapify each
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
}

func main() {
    arr := []int{4, 10, 3, 5, 1}
    buildHeap(arr)
    // Print heap as array
    for i, v := range arr {
        if i > 0 {
            fmt.Print(" -> ")
        }
        fmt.Print(v)
    }
    fmt.Println(" -> null")
}

if left < n && arr[left] > arr[largest] {

Check if left child is larger than current largest

if right < n && arr[right] > arr[largest] {

Check if right child is larger than current largest

if largest != i {

If root is not largest, swap and heapify subtree

for i := n/2 - 1; i >= 0; i-- {

Start heapify from last non-leaf node up to root

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 buildHeap runs in linear time

Space: O(log n) due to recursion stack in heapify calls

vs Alternative: Naive approach inserting elements one by one into heap takes O(n log n), so buildHeap is more efficient

Edge Cases

empty array

No operations performed, heap remains empty

DSA Go

for i := n/2 - 1; i >= 0; i-- {

array with one element

Heapify called once but no swaps needed, array remains same

DSA Go

for i := n/2 - 1; i >= 0; i-- {

array with all equal elements

No swaps needed, heap property already holds

DSA Go

if largest != i {

When to Use This Pattern

When you need to build a heap from an unordered array efficiently, use the bottom-up heapify approach starting from the last non-leaf node.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last non-leaf node
Fix: Start from index n/2 - 1 and move backwards to root

Mistake: Not recursively heapifying after swap
Fix: Call heapify recursively on the affected child index after swapping

Summary

Build Heap from Array Heapify converts an unordered array into a max heap by fixing subtrees from bottom up.

Use it when you want to efficiently create a heap from a list of elements.

The key insight is starting heapify from the last non-leaf node and moving upwards ensures 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 find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   The heapify process rearranges elements to ensure this property holds for every subtree starting from a given 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:

• Confusing heapify with sorting
• Thinking heapify finds max element only
• Assuming heapify reverses array

2. Which of the following is the correct way to call heapify on a node index i in Go when building a max heap from an array arr of size n?

easy

A. heapify(n, arr, i)

B. heapify(i, arr, n)

C. heapify(arr, i, n)

D. heapify(arr, n, i)

Solution

1. Step 1: Understand heapify function parameters

   Heapify usually takes the array, size of heap, and the index to heapify as parameters in that order.

2. Step 2: Match parameter order

   heapify(arr, n, i) matches the correct order: array, size, index.

3. Final Answer:

   heapify(arr, n, i) -> Option D

4. Quick Check:

   heapify(arr, n, i) is correct call [OK]

Hint: Remember: heapify(array, size, index) [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. Given the array [3, 9, 2, 1, 4, 5], what is the array after building a max heap using heapify from the bottom up?

medium

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

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

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

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

Solution

1. Step 1: Start heapify from last non-leaf node

   Last non-leaf node index = n/2 -1 = 6/2 -1 = 2. Heapify nodes 2, 1, 0 in order.

2. Step 2: Heapify index 2

   Node 2 value=2, children 5 (index 5). Swap 2 and 5. Array becomes [3, 9, 5, 1, 4, 2].

3. Step 3: Heapify index 1

   Node 1 value=9, children 1 and 4. 9 is largest, no change.

4. Step 4: Heapify index 0

   Node 0 value=3, children 9 and 5. Swap 3 and 9. Array becomes [9, 3, 5, 1, 4, 2]. Heapify index 1 again: 3 with children 1 and 4, swap 3 and 4. Final array: [9, 4, 5, 1, 3, 2].

5. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option C

6. Quick Check:

   Bottom-up heapify gives [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up swaps to fix largest child first [OK]

Common Mistakes:

• Not heapifying children after swap
• Starting heapify from wrong index
• Confusing max-heap with min-heap

4. Consider this Go code snippet to build a max heap from array arr. What is the error?

func buildHeap(arr []int) {
    n := len(arr)
    for i := n / 2; i >= 0; i-- {
        heapify(arr, n, i)
    }
}

medium

A. heapify function is missing the array size parameter

B. The loop should start from n/2 - 1, not n/2

C. The loop should increment i, not decrement

D. The loop condition should be i > 0, not i >= 0

Solution

1. Step 1: Identify correct start index for heapify

   Heapify starts from last non-leaf node at index n/2 - 1, not n/2.

2. Step 2: Analyze loop range

   Starting at n/2 includes one extra index which is a leaf node, unnecessary and may cause incorrect behavior.

3. Final Answer:

   The loop should start from n/2 - 1, not n/2 -> Option B

4. Quick Check:

   Start heapify at n/2 - 1 [OK]

Hint: Start heapify at last non-leaf node: n/2 - 1 [OK]

Common Mistakes:

• Starting loop at n/2 instead of n/2 - 1
• Loop increment instead of decrement
• Wrong loop condition excluding index 0

5. You have an array [4, 10, 3, 5, 1]. After building a max heap using heapify, you want to insert a new element 15 and maintain the max heap property. Which sequence of operations correctly maintains the heap?

hard

A. Append 15, then bubble up the new element until heap property is restored

B. Append 15, then heapify only the root node

C. Append 15, then heapify from last non-leaf node down to root

D. Replace root with 15, then heapify entire array

Solution

1. Step 1: Understand insertion in heap

   To insert, add element at end, then restore heap by bubbling up (swapping with parent if larger).

2. Step 2: Why bubble up?

   Heapify from bottom up is for building heap initially; for insertion, bubbling up fixes heap efficiently.

3. Final Answer:

   Append 15, then bubble up the new element until heap property is restored -> Option A

4. Quick Check:

   Insert + bubble up maintains heap [OK]

Hint: Insert at end, bubble up to fix heap [OK]

Common Mistakes:

• Using heapify from root after insertion
• Heapifying only root node
• Replacing root without adjusting heap