Heap Sort Algorithm in DSA Go

Mental Model

Heap sort organizes data into a special tree shape called a heap, then repeatedly removes the largest item to sort the list.

Analogy: Imagine a pile of boxes stacked so the biggest box is always on top. You take the biggest box off one by one to get a sorted line of boxes from biggest to smallest.

Array: [4, 10, 3, 5, 1]
Heap (max-heap):
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

Input: list: [4, 10, 3, 5, 1]

Goal: Sort the list in ascending order using heap sort

Step 1: Build max heap from the array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root (start) to prepare for sorting

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move the largest element to its correct final position at the end

Step 3: Heapify root to restore max heap property

[5, 4, 3, 1, 10]

Why: Fix the heap so the largest element is again at the root for next extraction

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place the next largest element in its final position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for next extraction

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element correctly

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap is already valid, no change needed

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element correctly

Step 9: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap size is 1, no heapify needed

Result:

[1, 3, 4, 5, 10] -- sorted array in ascending order

Annotated Code

DSA Go

package main

import "fmt"

// heapify maintains the max heap property for subtree rooted at i
func heapify(arr []int, n int, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    // check if left child exists and is greater than root
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // check if right child exists and is greater than current largest
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // if largest is not root, swap and continue heapifying
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest) // recursive call to fix subtree
    }
}

// heapSort sorts the array in ascending order using heap sort
func heapSort(arr []int) {
    n := len(arr)

    // build max heap
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i) // heapify each non-leaf node
    }

    // extract elements from heap one by one
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0] // move current root to end
        heapify(arr, i, 0)              // heapify reduced heap
    }
}

func main() {
    arr := []int{4, 10, 3, 5, 1}
    heapSort(arr)
    for i, v := range arr {
        if i == len(arr)-1 {
            fmt.Print(v)
        } else {
            fmt.Print(v, ", ")
        }
    }
    fmt.Println()
}

for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) }

build max heap by heapifying all non-leaf nodes from bottom up

for i := n - 1; i > 0; i-- { arr[0], arr[i] = arr[i], arr[0]; heapify(arr, i, 0) }

extract max element to end and restore heap for remaining elements

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

swap root with largest child and recursively heapify subtree

Output

1, 3, 4, 5, 10

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n extractions takes O(log n) to heapify

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Heap sort is more efficient than simple selection or bubble sort (O(n^2)) and uses less memory than merge sort (O(n))

Edge Cases

empty array

function returns immediately without changes

DSA Go

n := len(arr) // if n=0, loops do not execute

array with one element

array remains unchanged as it is already sorted

DSA Go

for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) } // loop runs zero times

array with duplicate elements

duplicates are handled normally and appear in sorted output

DSA Go

if left < n && arr[left] > arr[largest] { largest = left } // comparison handles duplicates

When to Use This Pattern

When you need to sort data efficiently in place and can use a tree-like structure, heap sort is a good choice because it uses a max heap to repeatedly select the largest element.

Common Mistakes

Mistake: Not building the max heap before sorting
Fix: Add the initial heap building loop that heapifies all non-leaf nodes

Mistake: Not reducing the heap size after swapping the root with the last element
Fix: Pass the reduced heap size to heapify to avoid including sorted elements

Mistake: Heapifying from the root only once instead of recursively
Fix: Call heapify recursively on the affected subtree after swapping

Summary

Heap sort organizes the array into a max heap and repeatedly extracts the largest element to sort the array.

Use heap sort when you want an in-place, comparison-based sorting algorithm with guaranteed O(n log n) time.

The key insight is building a max heap so the largest element is always at the root, making extraction straightforward.