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.4k Golang : Select region of interest with mouse click and crop from image
+23.6k Golang : Get current file path of a file or executable
+4.2k Golang : Calculate half life decay example
+8k Golang : Inject/embed Javascript before sending out to browser example
+7.9k Golang : Find the length of big.Int variable example
+6k Golang : Get Alexa ranking data example
+11.4k Golang : Exit, terminating or aborting a program
+10.5k Golang : Change date format to yyyy-mm-dd
+3.5k Javascript : Detect when console is activated and do something about it
+22.1k Golang : Fix type interface{} has no field or no methods and type assertions example
+6k Golang : Squaring elements in array
+9.5k Golang : How to transmit update file to client by HTTP request example