Heap Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Heap Sort on a small array

What is the output of the following Go code that performs heap sort on the array [4, 10, 3, 5, 1]?

DSA Go

package main

import "fmt"

func heapify(arr []int, n int, 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, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)

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

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

func main() {
    arr := []int{4, 10, 3, 5, 1}
    heapSort(arr)
    fmt.Println(arr)
}

A [1 4 3 5 10]

B [1 3 4 5 10]

C [10 5 4 3 1]

D [3 4 5 10 1]

💡 Hint

Heap sort sorts the array in ascending order by building a max heap first.

The heap sort algorithm first builds a max heap, then repeatedly swaps the root with the last element and heapifies the reduced heap. This results in a sorted array in ascending order.

🧠 Conceptual

intermediate

Heap Sort Time Complexity Explanation

Which of the following best describes the time complexity of heap sort and why?

A O(n log n) because building the heap takes O(n) and each of the n removals takes O(log n)

B O(n^2) because heapify is called n times and each call takes O(n)

C O(log n) because heap operations are logarithmic and done once

D O(n) because heap sort only scans the array twice

💡 Hint

Consider the cost of building the heap and the cost of extracting elements.

Building the heap takes O(n) time, and then removing the largest element n times takes O(n log n) total. So overall time complexity is O(n log n).

🔧 Debug

advanced

Identify the bug in heapify function

What error will occur when running this heapify function on an array, and why?

DSA Go

func heapify(arr []int, n int, 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, largest)
    }
}

A Infinite recursion because largest is never updated

B No error, function works correctly

C Index out of range error because left and right child indices are calculated incorrectly

D Type error due to wrong variable types

💡 Hint

Check how left and right child indices are calculated in a heap stored in an array.

The left and right child indices in a zero-based array heap should be 2*i + 1 and 2*i + 2. Using 2*i and 2*i + 1 causes out of range access.

🚀 Application

advanced

Heap Sort Stability

Is heap sort a stable sorting algorithm? Choose the correct explanation.

A No, because heap sort swaps elements that can change the relative order of equal elements

B Yes, because heap sort only swaps adjacent elements

C No, because heap sort uses extra memory that disrupts stability

D Yes, because heap sort uses a heap which preserves order

💡 Hint

Consider what happens when equal elements are swapped during heapify.

Heap sort is not stable because it swaps elements that may be far apart, which can change the relative order of equal elements.

❓ Predict Output

expert

Heap Sort Output with Duplicate Elements

What is the output of the following Go code after heap sorting the array [2, 3, 3, 1, 2]?

DSA Go

package main

import "fmt"

func heapify(arr []int, n int, 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, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)

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

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

func main() {
    arr := []int{2, 3, 3, 1, 2}
    heapSort(arr)
    fmt.Println(arr)
}

A [2 1 2 3 3]

B [3 3 2 2 1]

C [1 2 3 2 3]

D [1 2 2 3 3]

💡 Hint

Heap sort sorts all elements in ascending order regardless of duplicates.

Heap sort will sort the array in ascending order including duplicates, resulting in [1 2 2 3 3].