## Algorithms in Go: Heap Sort

Posted on January 12, 2020 | 3 minute read### Introduction

Heap Sort is a sorting algorithms which uses the Heap data structure to arrange a set of elements in an ascending or descending order.

In a previous post I have shown how to build a Max Heap. I suggest that you check it out first before continuing with the sorting algorithm.

https://fodor.org/blog/go-heap/

As you know now, there are two main types of heaps: Max Heap and Min Heap. Once we have implemented those, it is a trivial matter to do the sorting.

In a Max Heap, we are going to always have the largest element at the top, followed by the smaller ones. And in a Min Heap, the opposite is going to be true. Hence we are going to use the Max Heap for sorting in a descending order and the Min Heap for sorting in an ascending order.

### Time complexity

The time complexity of a heap sort is O(*n* lg *n*), since the initial processing of the input into a heap takes O(*n*) and for every element extraction we need to make adjustments that take O(lg *n* ).

### How does it work?

If we want to sort a set of elements in ascending order then we:

- Create a Min Heap from the elements. This is going to place the smallest element at the top.
- Extract the minimum (top) element until we exhaust the heap and place them in a new array/slice, sequentially.
- The resulting array/slice will automatically be sorted in an ascending order.

The sort in a descending order, we are going to follow the same steps as above, but instead will create a Max Heap.

### Implementation

In this implementation, I have used the Heap data structures I have created earlier and created two methods: `SortAscending`

and `SortDescending`

.

```
package heapsort
import (
"github.com/dorin131/go-data-structures/maxheap"
"github.com/dorin131/go-data-structures/minheap"
)
// SortAscending : sort ascending a slice of integers using Heap Sort
func SortAscending(input []int) []int {
result := []int{}
mh := minheap.New(input)
for range input {
result = append(result, mh.ExtractMin())
}
return result
}
// SortDescending : sort descending a slice of integers using Heap Sort
func SortDescending(input []int) []int {
result := []int{}
mh := maxheap.New(input)
for range input {
result = append(result, mh.ExtractMax())
}
return result
}
```

To test that our sorting works correctly, I have used Go’s built-in `sort`

library.

```
func TestSortAscending(t *testing.T) {
tests := []struct {
Given []int
}{
{[]int{4, 9, 10, 0, -4, 7}},
{[]int{1000, 100, 10, 0, -1000}},
{[]int{1, 1, 1, 1}},
{[]int{}},
{[]int{777}},
}
for n, test := range tests {
correctlySorted := make([]int, len(test.Given))
copy(correctlySorted, test.Given)
result := SortAscending(test.Given)
if len(result) != len(test.Given) {
t.Errorf("[%d] Lengths don't match", n)
return
}
sort.Slice(correctlySorted, func(i, j int) bool {
return correctlySorted[i] < correctlySorted[j]
})
for k := range correctlySorted {
if correctlySorted[k] != result[k] {
t.Errorf("[%v] Expected: %v, Got: %v\n", n, correctlySorted, result)
return
}
}
fmt.Printf("[%v] Correctly sorted: %v\n", n, result)
}
}
```

### Source code

https://github.com/dorin131/go-algorithms

### To follow

Stay tuned for the next post which is going to be on Priority Queues, which are also based on Heaps!

```
tags:go
algorithms
sort
heap sort
```