Golang : Heap sort example


Tags : golang heap-sort sorting recursive

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

  See also : Golang : Bubble sort example



Tags : golang heap-sort sorting recursive

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