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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Build Max-Heap from Array

What is the printed state of the array after building a max-heap using heapify on the input array?

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 < n && arr[left] > arr[largest] {
        largest = left
    }

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

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

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

func main() {
    arr := []int{3, 9, 2, 1, 4, 5}
    buildMaxHeap(arr)
    fmt.Println(arr)
}

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

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

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

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

💡 Hint

Remember that buildMaxHeap starts heapifying from the last non-leaf node upwards.

The buildMaxHeap function heapifies from the middle of the array towards the root, ensuring the max-heap property. After heapify, the largest element is at the root, and the array is rearranged accordingly.

❓ Predict Output

intermediate

Output of Build Min-Heap from Array

What is the printed state of the array after building a min-heap using heapify on the input array?

DSA Go

package main

import "fmt"

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

    if left < n && arr[left] < arr[smallest] {
        smallest = left
    }

    if right < n && arr[right] < arr[smallest] {
        smallest = right
    }

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

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

func main() {
    arr := []int{7, 2, 6, 3, 9, 1}
    buildMinHeap(arr)
    fmt.Println(arr)
}

A [1, 2, 3, 7, 9, 6]

B [1, 2, 6, 3, 9, 7]

C [2, 3, 1, 7, 9, 6]

D [1, 3, 2, 6, 7, 9]

💡 Hint

Build min-heap by heapifying from last non-leaf node upwards, ensuring smallest element at root.

The buildMinHeap function heapifies the array so that the smallest element is at the root and the min-heap property is maintained throughout the tree.

🔧 Debug

advanced

Identify the Bug in Heapify Function

What error will occur when running this heapify function on an array?

DSA Go

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

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

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

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

A Index out of range runtime panic

B No error, runs correctly

C Compilation error due to missing return

D Stack overflow due to infinite recursion

💡 Hint

Check how left and right child indices are calculated for a zero-based array.

The left and right child indices are incorrectly calculated as 2*i and 2*i+1 instead of 2*i+1 and 2*i+2, causing out-of-range access for i=0.

❓ Predict Output

advanced

Resulting Array After Partial Heapify

Given the array and a call to heapify at index 1, what is the resulting array?

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 < n && arr[left] > arr[largest] {
        largest = left
    }

    if right < n && arr[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}
    heapify(arr, len(arr), 1)
    fmt.Println(arr)
}

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

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

C 4, 10, 3, 5, 1]

D [4, 10, 3, 5, 1

💡 Hint

Check if the subtree rooted at index 1 needs rearrangement.

At index 1, the value is 10, children are 5 and 1 which are smaller, so no swaps happen. The array remains unchanged.

❓ Predict Output

expert

Final Array After Build Max-Heap on Large Input

What is the final array after building a max-heap from this input array?

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 < n && arr[left] > arr[largest] {
        largest = left
    }

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

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

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

func main() {
    arr := []int{12, 11, 13, 5, 6, 7, 17, 1, 8, 9}
    buildMaxHeap(arr)
    fmt.Println(arr)
}

A [13, 11, 17, 5, 6, 7, 12, 1, 8, 9]

B [17, 11, 13, 9, 6, 7, 12, 1, 8, 10]

C [17, 11, 13, 9, 6, 7, 12, 1, 8, 5]

D [17, 13, 12, 9, 11, 7, 6, 1, 8, 5]

💡 Hint

Build max-heap by heapifying from last non-leaf node upwards.

After heapify, the largest element 17 is at root, and the array is rearranged to maintain max-heap property.