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
+11.9k Android Studio : Password input and reveal password example
+10k Golang : Intercept and process UNIX signals example
+13.2k Golang : Overwrite previous output with count down timer
+15k Golang : convert string or integer to big.Int type
+7.4k Golang: Prevent over writing file with md5 hash
+13.8k Golang : How to check if IP address is in range
+4.7k Golang : ROT32768 (rotate by 0x80) UTF-8 strings example
+3.2k Detect if Google Analytics and Developer Media are loaded properly or not
+24.7k Golang : Get executable name behind process ID example
+7.1k Findstr command the Grep equivalent for Windows
+16.2k Golang : Find smallest number in array
+4.2k Python : Create Whois client or function example