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.