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.

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