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.