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.
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
dorin131 / go-algorithms
A collection of algorithms implemented in Go
go-algorithms
A collection of algorithms implemented in Go
- Insertion Sort
- Merge Sort
- Heap Sort
To follow
Stay tuned for the next post which is going to be on Priority Queues, which are also based on Heaps!
Top comments (0)