HeapSort in Go: Implementation and Performance Comparison

HeapSort is an efficient comparison-based sorting algorithm that utilizes a binary heap data structure. It has a time complexity of O(n log n) and does not require additional space, making it an in-place sorting algorithm.

Understanding HeapSort

HeapSort involves two main steps:

1. Build a Max-Heap: Convert the array into a max-heap, a complete binary tree where the value of each node is greater than or equal to the values of its children.
2. Extract Elements from the Heap: Repeatedly remove the maximum element from the heap (the root) and place it at the end of the array, then restore the heap property for the remaining elements.

Implementation of HeapSort in Go

Here is the implementation of HeapSort in Go:

go
package main

import (
    "fmt"
)

// HeapSort function
func HeapSort(arr []int) {
    n := len(arr)

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

    // One by one extract elements from the heap
    for i := n - 1; i > 0; i-- {
        // Move current root to end
        arr[0], arr[i] = arr[i], arr[0]

        // Call max heapify on the reduced heap
        heapify(arr, i, 0)
    }
}

// Heapify a subtree rooted at node i
func heapify(arr []int, n int, i int) {
    largest := i      // Initialize largest as root
    left := 2*i + 1   // Left child
    right := 2*i + 2  // Right child

    // If left child is larger than root
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // If right child is larger than largest so far
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // If largest is not root
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]  // Swap

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("Unsorted array:", arr)

    HeapSort(arr)
    fmt.Println("Sorted array:", arr)
}

Comparing HeapSort with Other Sorting Algorithms

Time Complexity

• HeapSort: O(n log n)
• QuickSort: Average case O(n log n), worst case O(n²)
• MergeSort: O(n log n)
• InsertionSort: Average and worst case O(n²)
• BubbleSort: Average and worst case O(n²)

Space Complexity

• HeapSort: O(1) (in-place sorting)
• QuickSort: O(log n) (due to recursive stack space)
• MergeSort: O(n) (requires additional space for merging)
• InsertionSort: O(1) (in-place sorting)
• BubbleSort: O(1) (in-place sorting)

Performance Characteristics

1. HeapSort

   • Pros:
     • Consistent O(n log n) time complexity.
     • In-place sorting (O(1) space complexity).
     • Not sensitive to input data order.
   • Cons:
     • Generally slower than QuickSort for average cases due to less efficient memory access patterns.
     • Not stable (relative order of equal elements may change).

2. QuickSort

   • Pros:
     • Very fast for average cases, often faster than HeapSort due to better cache performance.
     • In-place sorting (O(log n) space complexity).
   • Cons:
     • Worst-case time complexity is O(n²), although this can be mitigated with good pivot selection strategies.
     • Not stable.

3. MergeSort

   • Pros:
     • Consistent O(n log n) time complexity.
     • Stable sorting algorithm.
     • Excellent for linked lists and external sorting.
   • Cons:
     • Requires additional space (O(n)).
     • Slightly more complex to implement compared to HeapSort and QuickSort.

4. InsertionSort

   • Pros:
     • Simple and easy to implement.
     • Efficient for small datasets or nearly sorted data.
     • Stable sorting algorithm.
   • Cons:
     • Poor performance on large datasets (O(n²) time complexity).

5. BubbleSort

   • Pros:
     • Simple to understand and implement.
     • Stable sorting algorithm.
   • Cons:
     • Inefficient for large datasets (O(n²) time complexity).

Conclusion

HeapSort is a robust, in-place sorting algorithm with a consistent O(n log n) time complexity. It is especially useful when space is a constraint. However, for practical purposes, QuickSort is often preferred due to its faster average-case performance, despite its potential O(n²) worst-case time complexity. MergeSort is another solid choice, particularly when stability is required, although it comes with higher space requirements. Understanding the strengths and weaknesses of each algorithm allows you to choose the right one for your specific needs.