Introduction

Heap Sort is a popular sorting algorithm based on the binary heap data structure. It divides the input array into two parts: a sorted and an unsorted part. The sorted part is built from the largest element of the unsorted part and the process continues until all elements are sorted.

Program Structure

The program consists of the following key components:

• Heapify Function: Converts the array into a max heap.
• Heap Sort Function: Implements the sorting logic using the heap.
• Main Function: Initializes the array and calls the sorting function.

Heap Sort Code in Go

package main

import (
    "fmt"
)

// heapify creates a max heap from a slice of integers.
func heapify(arr []int, n int, i int) {
    largest := i // Initialize largest as root
    left := 2*i + 1 // left child index
    right := 2*i + 2 // right child index

    // 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)
    }
}

// HeapSort sorts the input slice using the heap sort algorithm.
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-- {
        arr[0], arr[i] = arr[i], arr[0] // swap
        heapify(arr, i, 0)
    }
}

// main function to execute the heap sort algorithm
func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("Unsorted array:", arr)

    HeapSort(arr)

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

Explanation of the Code

Heapify Function

The heapify function takes three parameters: the array arr, the size of the heap n, and the index i of the current node. It ensures that the subtree rooted at index i follows the max-heap property.

HeapSort Function

The HeapSort function starts by building a max heap from the input array. It then repeatedly swaps the root of the heap (the maximum element) with the last element of the heap and reduces the heap size by one, maintaining the max heap property in the process.

Main Function

In the main function, we define an unsorted array, print it, call the HeapSort function to sort the array, and then print the sorted array.

Conclusion

The Heap Sort algorithm is efficient and has a time complexity of O(n log n). This implementation in Go demonstrates the fundamental principles of heap sort while maintaining clarity and simplicity.