Heap Sort Algorithm in DSA Go - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.

🎯 Goal: Build a Go program that sorts a list of numbers using the heap sort algorithm step-by-step.

📋 What You'll Learn

Create an integer slice called numbers with the exact values: 12, 11, 13, 5, 6, 7

Create a variable n to store the length of numbers

Write a function heapify that maintains the max heap property for a subtree

Write the main heap sort logic using heapify to sort the slice

Print the sorted slice after heap sort completes

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in optimizing sorting tasks and is often asked in technical interviews for software engineering roles.

1

Create the initial data slice

Create a slice of integers called numbers with these exact values: 12, 11, 13, 5, 6, 7.

DSA Go

# Create the slice numbers with the given values
# Your code here

Hint

Use numbers := []int{12, 11, 13, 5, 6, 7} to create the slice.

2

Add length variable for the slice

Add a variable called n that stores the length of the numbers slice using len(numbers).

DSA Go

package main

func main() {
    numbers := []int{12, 11, 13, 5, 6, 7}
    // Create variable n to store length of numbers
    // Your code here
}

Hint

Use n := len(numbers) to get the length.

3

Write the heapify function

Write a function called heapify that takes a slice arr []int, an integer n for the size, and an integer i for the root index. This function should maintain the max heap property by comparing the root with its children and swapping if needed.

DSA Go

package main

func main() {
    numbers := []int{12, 11, 13, 5, 6, 7}
    n := len(numbers)
}

// heapify maintains max heap property for subtree rooted at i
func heapify(arr []int, n int, i int) {
    // Your code here
}

Hint

Use recursion to call heapify again if a swap happens.

4

Implement heap sort and print the sorted slice

In the main function, implement heap sort by first building a max heap using heapify for all non-leaf nodes, then repeatedly swap the root with the last element and reduce the heap size, calling heapify each time. Finally, print the sorted numbers slice using fmt.Println(numbers).

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{12, 11, 13, 5, 6, 7}
    n := len(numbers)

    // Build max heap
    // Your code here

    // Extract elements from heap one by one
    // Your code here

    // Print sorted slice
    // Your code here
}

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)
    }
}

Hint

Remember to build the max heap first, then swap the root with the last element and heapify the reduced heap repeatedly.