Heap Sort Algorithm in Golang

1. Introduction

Heap Sort is a comparison-based sorting algorithm that uses binary heap data structures. The primary idea behind heap sort is to turn the array into a max-heap structure, which ensures that the largest element is at the root. Once the heap structure is formed, the root element can be replaced with the last item of the heap followed by reducing the size of the heap by one. This procedure is repeated until the size of the heap is one.

2. Implementation Steps

1. Build a max-heap from the input array.

2. Swap the root element with the last item of the heap (last element of the array).

3. Reduce the size of the heap by one, leaving the largest item at the end of the sorted section of the array.

4. Heapify the root element.

5. Repeat steps 2 to 4 until the heap size is one.

3. Implementation in Golang

package main
import (
	"fmt"
)
func heapify(arr []int, n, i int) {
	largest := i          // Initialize largest as root
	l := 2*i + 1          // left child index
	r := 2*i + 2          // right child index
	// Check if left child exists and is greater than root
	if l < n && arr[l] > arr[largest] {
		largest = l
	}
	// Check if right child exists and is greater than largest
	if r < n && arr[r] > arr[largest] {
		largest = r
	}
	// If the largest isn't root
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}
func heapSort(arr []int) {
	n := len(arr)
	// Build a max heap
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}
	// Extract elements from heap one by one
	for i := n - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}
func main() {
	data := []int{12, 11, 13, 5, 6, 7}
	fmt.Println("Original array:", data)
	heapSort(data)
	fmt.Println("Sorted array:  ", data)
}

Output:

Original array: [12 11 13 5 6 7]
Sorted array:   [5 6 7 11 12 13]

Explanation:

1. The heapify function is a helper to maintain the max-heap property. Given a binary heap, it ensures that the subtree rooted at a given index i maintains the max-heap property.

2. The heapSort function first builds a max-heap from the input array. This is done because, with a max-heap, the largest element is at the root. It then repeatedly extracts the maximum from the heap and reconstructs the heap.

3. Inside the main function, an array is initialized, displayed in its original state, sorted using heapSort, and then displayed in its sorted state.

4. The efficiency of Heap Sort is O(n log n) for all cases which makes it quite useful for sorting large datasets.

This provides a detailed understanding of the Heap Sort algorithm in Golang.