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.6k Golang : Merge video(OpenCV) and audio(PortAudio) into a mp4 file
+18.4k Golang : Convert(cast) bytes.Buffer or bytes.NewBuffer type to io.Reader
+34.3k Golang : Validate IP address
+24.5k Golang : How to write CSV data to file
+9.5k Golang : Underscore string example
+7k Golang : Randomize letters from a string example
+4.3k Golang : Pad file extension automagically
+7.9k Golang : How to use Gorilla webtoolkit context package properly
+18.7k Android Studio : AlertDialog and EditText to get user string input example
+20.9k Fix "Failed to start php5-fpm.service: Unit php5-fpm.service is masked."
+6.8k Gogland : Where to put source code files in package directory for rookie