# 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.

## Comments

## Post a Comment