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
+15.7k Golang : Set, Get and List environment variables
+5.5k Gogland : Single File versus Go Application Run Configurations
+3.9k Golang : Calculate diameter, circumference, area, sphere surface and volume
+6.2k PHP : Get coordinates latitude/longitude from string
+6.3k Golang : How to get garbage collection data?
+4.6k Golang : Configure Apache and NGINX to access your Go service example
+18.7k Golang : Convert(cast) string to rune and back to string example
+16.6k Golang : Get password from console input without echo or masked
+8.9k Golang : rune literal not terminated error
+2.8k Golang : A program that contain another program and executes it during run-time
+19.1k PHP : Convert(cast) string to bigInt
+4.1k Nginx : Password protect a directory/folder