Heapsort in Go, inspired by <Algorithm 4th> Robert S.

heapsort.go

package main

/*
	Follow graph on http://algs4.cs.princeton.edu/24pq/
	for viewing heap structure.
	p.s. Heap is of binary tree form with root at index 1
		 Index spread out by tree's level order (left to right, up to down.
*/

import (
	"fmt"
)

//TODO: more generics param need to fit in here @_@
type IntSlice [10]int

func sink(pq *IntSlice, k int, N int) {
	for 2*k <= N {
		j := 2 * k
		if j < N && less(pq, j, j+1) {
			j++
		}
		if !less(pq, k, j) {
			break
		}
		exch(pq, k, j)
		k = j
	}
}

//index off by 1 because of heap structure.
func less(pq *IntSlice, i int, j int) bool {
	return (pq[i-1] - pq[j-1]) < 0
}

func exch(pq *IntSlice, i int, j int) {
	var swap = pq[i-1]
	pq[i-1] = pq[j-1]
	pq[j-1] = swap
}

func show(a *IntSlice) {
	for i := 0; i < len(a); i++ {
		fmt.Println(a[i])
	}
}

func heapsort(pq *IntSlice) {
	N := len(pq)
	for k := N / 2; k >= 1; k-- {
		sink(pq, k, N)
	}
	for N > 1 {
		exch(pq, 1, N)
		N--
		sink(pq, 1, N)
	}
}

func main() {
	a := IntSlice{3, 1, 2, 5, 7, 8, 4, 9, 6, 10}
	heapsort(&a)
	show(&a)
}