Build Heap from Array Heapify in DSA Go - Build from Scratch

Build Heap from Array Heapify

📖 Scenario: Imagine you have a list of numbers representing tasks with different priorities. You want to organize them so the highest priority task is always easy to find. This is like arranging a pile of books so the biggest book is always on top.

🎯 Goal: You will build a max heap from an unsorted array using the heapify process. This means rearranging the array so each parent number is bigger than its children.

📋 What You'll Learn

Create an integer slice called arr with the values 4, 10, 3, 5, 1

Create an integer variable called n to store the length of arr

Write a function called heapify that takes arr, n, and an index i and rearranges the elements to maintain max heap property

Use a for loop starting from the last parent node down to the root to call heapify on arr

Print the final heap array after building the max heap

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and efficient sorting algorithms like heap sort.

💼 Career

Understanding heaps is important for software engineers working on performance-critical applications, data processing, and algorithm design.

1

Create the initial array

Create an integer slice called arr with the values 4, 10, 3, 5, 1.

DSA Go

arr := []int{4, 10, 3, 5, 1} // Your code here

Hint

Use arr := []int{4, 10, 3, 5, 1} to create the slice.

2

Create a variable for the array length

Create an integer variable called n and set it to the length of arr.

DSA Go

package main

func main() {
    arr := []int{4, 10, 3, 5, 1}
    n := len(arr) // Your code here
}

Hint

Use n := len(arr) to get the length of the slice.

3

Write the heapify function and build the heap

Write a function called heapify that takes arr (slice of int), n (int), and i (int). It should rearrange elements to maintain the max heap property. Then, in main, use a for loop starting from n/2 - 1 down to 0 to call heapify(arr, n, i).

DSA Go

package main

func heapify(arr []int, n int, i int) {
    // Your code here
}

func main() {
    arr := []int{4, 10, 3, 5, 1}
    n := len(arr)
    // Your code here
}

Hint

Use the formula left = 2*i + 1 and right = 2*i + 2 to find children. Swap if child is bigger and call heapify recursively.

4

Print the final heap array

Print the arr slice after building the max heap using fmt.Println(arr).

DSA Go

package main

import "fmt"

func heapify(arr []int, n int, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left  arr[largest] {
        largest = left
    }

    if right  arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func main() {
    arr := []int{4, 10, 3, 5, 1}
    n := len(arr)

    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    fmt.Println(arr) // Your code here
}

Hint

Use fmt.Println(arr) to print the heap array.

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