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.

Practice

1. What is the main purpose of the heap in the Heap Sort algorithm?

easy

A. To efficiently find and remove the largest (or smallest) element

B. To store elements in sorted order permanently

C. To reverse the order of elements in the array

D. To count the number of elements in the array

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure where the parent node is either greater (max-heap) or smaller (min-heap) than its children, allowing quick access to the largest or smallest element.

2. Step 2: Role in Heap Sort

   Heap Sort uses this property to repeatedly extract the largest element from the heap and place it at the end of the array, sorting the array efficiently.

3. Final Answer:

   To efficiently find and remove the largest (or smallest) element -> Option A

4. Quick Check:

   Heap = fast max/min extraction [OK]

Hint: Heap helps quickly get max/min element for sorting [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with a simple array
• Believing heap reverses array order

2. Which of the following is the correct way to swap two elements in Go during Heap Sort?

easy

A. arr[i] = arr[j]; arr[j] = arr[i]

B. arr[i], arr[j] = arr[j], arr[i]

C. swap(arr[i], arr[j])

D. temp = arr[i]; arr[j] = arr[i]; arr[i] = temp

Solution

1. Step 1: Understand Go multiple assignment

   Go allows swapping two variables in one line using multiple assignment syntax: arr[i], arr[j] = arr[j], arr[i].

2. Step 2: Check other options

   swap(arr[i], arr[j]) is invalid syntax in Go. arr[i] = arr[j]; arr[j] = arr[i] overwrites arr[i] before assigning arr[j]. temp = arr[i]; arr[j] = arr[i]; arr[i] = temp incorrectly sets arr[j] to old arr[i] and leaves arr[i] unchanged.

3. Final Answer:

   arr[i], arr[j] = arr[j], arr[i] -> Option B

4. Quick Check:

   Go swap uses multiple assignment [OK]

Hint: Use Go's multiple assignment to swap variables [OK]

Common Mistakes:

• Using invalid swap function call
• Overwriting one element before swapping
• Using incorrect temp assignment sequence

3. What will be the output array after applying Heap Sort on [4, 10, 3, 5, 1]?

medium

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

B. [10, 5, 4, 3, 1]

C. [1, 4, 3, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Build max heap from array

   Heapify the array to get max heap: [10, 5, 3, 4, 1]

2. Step 2: Extract max and sort

   Repeatedly swap max with last element and heapify remaining: final sorted array is [1, 3, 4, 5, 10]

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option A

4. Quick Check:

   Heap Sort sorts ascending [OK]

Hint: Heap Sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Forgetting to heapify after swaps
• Assuming heap sort outputs descending order

4. Identify the bug in this Go heapify function snippet used in Heap Sort:

func heapify(arr []int, n, i int) {
  largest := i
  l := 2*i + 1
  r := 2*i + 2
  if l < n && arr[l] > arr[largest] {
    largest = l
  }
  if r < n && arr[r] > arr[largest] {
    largest = r
  }
  if largest != i {
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, i)
  }
}

medium

A. Swap syntax is invalid in Go

B. Indices l and r are calculated incorrectly

C. Recursive call should be heapify(arr, n, largest) instead of heapify(arr, n, i)

D. Function should return a value

Solution

1. Step 1: Analyze recursive call

   After swapping, heapify must continue from the new largest index to fix subtree, so call should be heapify(arr, n, largest).

2. Step 2: Check other parts

   Indices l and r are correct for binary heap. Swap syntax is valid Go. Function does not need to return value.

3. Final Answer:

   Recursive call should be heapify(arr, n, largest) instead of heapify(arr, n, i) -> Option C

4. Quick Check:

   Recursive call uses largest index [OK]

Hint: After swap, heapify from largest child index [OK]

Common Mistakes:

• Recursing on wrong index after swap
• Miscomputing child indices
• Thinking swap syntax is wrong in Go

5. Given an array with many duplicate values, how does Heap Sort behave compared to Quick Sort in terms of stability and performance?

hard

A. Both Heap Sort and Quick Sort are stable and have same worst-case time

B. Heap Sort is stable and faster than Quick Sort always

C. Quick Sort is stable and always faster than Heap Sort

D. Heap Sort is not stable but has consistent O(n log n) time; Quick Sort is unstable and may degrade to O(n²)

Solution

1. Step 1: Understand stability and time complexity

   Heap Sort is not stable because it swaps elements that may change relative order. It guarantees O(n log n) time always.

2. Step 2: Compare with Quick Sort

   Quick Sort is also not stable and can degrade to O(n²) in worst case, but often faster on average.

3. Final Answer:

   Heap Sort is not stable but has consistent O(n log n) time; Quick Sort is unstable and may degrade to O(n²) -> Option D

4. Quick Check:

   Heap Sort stable? No; Quick Sort worst-case O(n²) [OK]

Hint: Heap Sort always O(n log n), unstable; Quick Sort can be slower [OK]

Common Mistakes:

• Assuming Heap Sort is stable
• Thinking Quick Sort is always faster
• Confusing stability with sorting speed