Golang : Heap sort example
Heapsort algorithm divides the unsorted data into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. Below is an example of Heapsort implementation in Golang.
package main
import (
"fmt"
)
func maxHeapify(tosort []int, position int) {
size := len(tosort)
maximum := position
leftChild := 2*position + 1
rightChild := leftChild + 1
if leftChild < size && tosort[leftChild] > tosort[position] {
maximum = leftChild
}
if rightChild < size && tosort[rightChild] > tosort[maximum] {
maximum = rightChild
}
if position != maximum {
tosort[position], tosort[maximum] = tosort[maximum], tosort[position]
maxHeapify(tosort, maximum) //recursive
}
}
func buildMaxHeap(tosort []int) {
// from http://en.wikipedia.org/wiki/Heapsort
// iParent = floor((i-1) / 2)
for i := (len(tosort) - 1) / 2; i >= 0; i-- {
maxHeapify(tosort, i)
}
}
func heapSort(tosort []int) {
buildMaxHeap(tosort)
for i := len(tosort) - 1; i >= 1; i-- {
tosort[i], tosort[0] = tosort[0], tosort[i]
maxHeapify(tosort[:i-1], 0)
}
}
func main() {
unsorted := []int{99, 55, 33, 67, 9, 5, 431, 999, 8108, 108}
fmt.Println("Before : ", unsorted)
heapSort(unsorted)
fmt.Println("After : ", unsorted)
}
Output :
Before : [99 55 33 67 9 5 431 999 8108 108]
After : [9 5 33 55 67 99 108 431 999 8108]
Reference :
See also : Golang : Bubble sort example
By Adam Ng
IF you gain some knowledge or the information here solved your programming problem. Please consider donating to the less fortunate or some charities that you like. Apart from donation, planting trees, volunteering or reducing your carbon footprint will be great too.
Advertisement
Tutorials
+9.5k Facebook : Getting the friends list with PHP return JSON format
+6.3k Golang : Calculate US Dollar Index (DXY)
+14.6k Golang : Missing Bazaar command
+6.1k Golang : Measure execution time for a function
+20.8k Android Studio : AlertDialog and EditText to get user string input example
+5.8k Golang : Error handling methods
+6.4k Golang : Selection sort example
+7.2k Golang : Get environment variable
+30.9k Golang : Download file example
+4.8k Golang : How to pass data between controllers with JSON Web Token
+13.9k Golang : Convert spaces to tabs and back to spaces example
+26.9k Golang : Convert file content into array of bytes