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 :

http://en.wikipedia.org/wiki/Heapsort