Heap Sort in Go

HeapSort.go

package main

import (
	"fmt"
	"math/rand"
	"time"
	"errors"
	"log"
)

const MaxHeapSize = 15

type Heap interface {
	Insert(val int) error
	PopMin() (int, error)

	PrintArray()
	PopAndPrintAll()
}

type ArrayHeap struct {
	array [MaxHeapSize]int
	size int
}

func (h *ArrayHeap) Insert(val int) error {
	if h.size >= MaxHeapSize {
		err := errors.New("Attempt to insert into a full ArrayHeap.")
		return err
	} else {
		e := h.size

		h.array[e] = val
		h.size += 1

		h.bubble_up(e)
		return nil
	}
}

func (h *ArrayHeap) PopMin() (int, error) {
	if h.size <= 0 {
		err := errors.New("Attempt to pop from an empty heap.")
		return -1, err
	} else {
		min := h.array[0]

		h.array[0] = h.array[h.size - 1]
		h.size -= 1
		h.bubble_down(0)

		return min, nil
	}
}

// func swap(x, y *int) {
// 	t := x
// 	y = x
// 	x = t
// }
func swap(x, y int) (int, int) {
	return y, x
}

func (h *ArrayHeap) bubble_up(e int) {
	if e <= 0 {
		return
	}

	e_p := e/2

	if h.array[e_p] > h.array[e] {
		h.array[e_p], h.array[e] = swap(h.array[e_p], h.array[e])
		h.bubble_up(e_p)
	}
}

func (h *ArrayHeap) bubble_down(e int) {
	min_e := e
	e_lchild := e*2
	e_rchild := e*2 + 1

	// check if min_e is great than its left child
	if e_lchild <= h.size {
		if h.array[min_e] > h.array[e_lchild] {
			min_e = e_lchild
		}
	}
	// check if min_e is great than its right child
	if e_rchild <= h.size {
		if h.array[min_e] > h.array[e_rchild] {
			min_e = e_rchild
		}
	}

	if min_e != e {
		h.array[min_e], h.array[e] = swap(h.array[min_e], h.array[e])
		h.bubble_down(min_e)
	}
}

func (h *ArrayHeap) PrintArray() {
	fmt.Print("[")
	for i := 0 ; i < h.size ; i++ {
		fmt.Print(h.array[i])
		if i < (h.size - 1) {
			fmt.Print(", ")
		}
	}
	fmt.Println("]")
}

// Pop all elements and print to screen
func (h *ArrayHeap) PopAndPrintAll() {
	fmt.Print("[")
	sz :=  h.size
	for i := 0 ; i < sz ; i++ {
		min, err := h.PopMin()
		if err != nil {
			fmt.Print("\nError: ")
			log.Fatal(err)
		}
		fmt.Print(min)
		if i < (sz - 1) {
			fmt.Print(", ")
		}
	}
	fmt.Println("]")
}

// Test a Heap implementation on randomly generated data
// h : a Heap
// n : the number of tests you want to
func TestHeap(h Heap, n int) {
	rand.Seed( time.Now().UTC().UnixNano())

	for i := 0 ; i < n ; i++ {
		fmt.Println("Running test ", i+1)
		fmt.Print("Insert order:  [")
		for k := 0 ; k < MaxHeapSize ; k++ {
			v := int(rand.Int31n(100))
			err := h.Insert(v)
			if err != nil {
				fmt.Print("\nError: ")
				log.Fatal(err)
			}

			fmt.Print(v)
			if k < (MaxHeapSize - 1) {
				fmt.Print(", ")
			}
		}
		fmt.Println("]")
		fmt.Print("Heap array:    ")
		h.PrintArray()
		fmt.Print("Sorted dump:   ")
		h.PopAndPrintAll()	
		fmt.Println()
	}
}

func main() {
	h := new(ArrayHeap)
	TestHeap(h, 7)
}