GoLang Heap and Heapsort

So I'm trying to implement a max heap for practice so I can get familiar with Go.

type MaxHeap struct {
	slice []int
	heapSize int
}
func BuildMaxHeap(slice []int) MaxHeap{
	h := MaxHeap{slice: slice, heapSize: len(slice)}
	for i := len(slice)/2; i >= 0; i-- {
		h.MaxHeapify(i)
	}
	return h
}

func (h MaxHeap) MaxHeapify(i int) {
	left := 2*i
	right := 2*i + 1
	largest := i
	slice := h.slice

	if left < h.size() {
		if slice[left] > slice[i] {
			largest = left
		} else {
			largest = i
		}
	}
	if right < h.size() {
		if slice[right] > slice[largest] {
			largest = right
		}
	}
	if largest != i {
		prevLargest := slice[i]
		slice[i] = slice[largest]
		slice[largest] = prevLargest
		h.MaxHeapify(largest)
	}
}

On an array of [4,1,3,2,16,9,10,14,8,7] I produce [16 14 9 10 8 1 4 2 3 7]

which is wrong as the 9 is one level too high and should be switched with the 10.

Where am I going wrong?

I also know something is weird, because when I try and heapsort

func heapSort(slice []int) []int {
	h := BuildMaxHeap(slice)
	fmt.Println(slice)
	for i := len(h.slice) - 1; i >=1 ; i-- {
		first := h.slice[0]
		last := h.slice[i]
		h.slice[0] = last
		h.slice[i] = first
		h.heapSize--
		h.MaxHeapify(1)
	}
	return h.slice
}

It does not work.

The issue was that slice indexes start at zero so your:

left := 2*i
right := 2*i + 1

gives a left child of 0 for index 0 (i.e., itself).
Just add one to each of those.

Your heapSort had a similar issue calling h.MaxHeapify(1) instead of 0. That effectively left whatever value was at the front there.

Here is a modified version of your code that works (test file also included that uses testing/quick to verify it against container/heap and sort).

heap.go:

package main

import "fmt"

type MaxHeap struct {
    slice    []int
    heapSize int
}

func BuildMaxHeap(slice []int) MaxHeap {
    h := MaxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice) / 2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h MaxHeap) MaxHeapify(i int) {
    l, r := 2*i+1, 2*i+2
    max := i

    if l < h.size() && h.slice[l] > h.slice[max] {
        max = l
    }
    if r < h.size() && h.slice[r] > h.slice[max] {
        max = r
    }
    //log.Printf("MaxHeapify(%v): l,r=%v,%v; max=%v\t%v\n", i, l, r, max, h.slice)
    if max != i {
        h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
        h.MaxHeapify(max)
    }
}

func (h MaxHeap) size() int { return h.heapSize } // ???

func heapSort(slice []int) []int {
    h := BuildMaxHeap(slice)
    //log.Println(slice)
    for i := len(h.slice) - 1; i >= 1; i-- {
        h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
        h.heapSize--
        h.MaxHeapify(0)
    }
    return h.slice
}

func main() {
    s := []int{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}
    h := BuildMaxHeap(s)
    fmt.Println(h)

    s = heapSort(s)
    fmt.Println(s)
}

<kbd>Playground</kbd>

heap_test.go:

package main

import (
    "container/heap"
    "reflect"
    "sort"
    "testing"
    "testing/quick"
)

// Compare against container/heap implementation:
// https://golang.org/pkg/container/heap/#example__intHeap

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] > h[j] } // use > for MaxHeap
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func TestMaxHeap(t *testing.T) {
    f := func(s []int) bool {
        //t.Log("testing heap len", len(s))
        h := BuildMaxHeap(s)
        h2 := make(IntHeap, len(h.slice))
        copy(h2, h.slice)
        for i := range h2 {
            heap.Fix(&h2, i)
        }
        eq := reflect.DeepEqual(h.slice, []int(h2))
        if !eq {
            t.Logf("MaxHeap: %v\n\t IntHeap: %v", h.slice, h2)
        }
        return eq
    }
    if err := quick.Check(f, nil); err != nil {
        t.Error(err)
    }
}

func TestHeapSort(t *testing.T) {
    f := func(s []int) bool {
        s = heapSort(s)
        return sort.IntsAreSorted(s)
    }
    if err := quick.Check(f, nil); err != nil {
        t.Error(err)
    }
}

Here's a way to do the same thing without the addition of the structure to hold the data and heapsize:

// AS described in Introduction to Algorithms (3rd Edition)
package main
import (
"fmt"
)
func left(i int) int {
return 2 * i
}
func right(i int) int {
return 2*i + 1
}
func parent(i int) int {
return i / 2
}
func maxHeapify(a []int, i int) []int {
fmt.Printf("Array: %v\n", a)
l := left(i) + 1
r := right(i) + 1
var largest int
if l < len(a) && l >= 0 && a[l] > a[i] {
largest = l
} else {
largest = i
}
if r < len(a) && r >= 0 && a[r] > a[largest] {
largest = r
}
if largest != i {
fmt.Printf("Exchanging: %d index (%d) with %d index (%d)\n", a[i], i, a[largest], largest)
a[i], a[largest] = a[largest], a[i]
a = maxHeapify(a, largest)
}
return a
}
func buildMaxHeap(a []int) []int {
for i := len(a)/2 - 1; i >= 0; i-- {
fmt.Printf("Building: %d index %d\n", a[i], i)
a = maxHeapify(a, i)
}
return a
}
func heapsort(a []int) []int {
a = buildMaxHeap(a)
fmt.Printf("Starting sort ... array is %v\n", a)
size := len(a)
for i := size - 1; i >= 1; i-- {
a[0], a[i] = a[i], a[0]
size--
maxHeapify(a[:size], 0)
}
return a
}
func main() {
a := [10]int{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}
fmt.Printf("Array: %v\n", a)
b := heapsort(a[:])
fmt.Printf("Array: %v\n", b)
}