Go Min Heap

min_heap.go

package main

import "log"

type MinHeap struct {
	arr  []int
	size int
}

func (mh *MinHeap) Insert(d int) {
	mh.arr = append(mh.arr, d)
	i := mh.size
	mh.size++
	if mh.size == 1 {
		return
	}

	for mh.arr[i] < mh.arr[parent(i)] {
		mh.swap(&mh.arr, i, parent(i))
		i = parent(i)
	}
}
func parent(index int) int {
	return (index - 1) / 2
}

func (mh MinHeap) Min() int {
	if mh.size == 0 {
		return 0
	}
	return mh.arr[0]
}

func (mh *MinHeap) ExtractMin() int {
	if mh.size == 0 {
		return 0
	}
	val := mh.arr[0]
	if mh.size == 1 {
		mh.size--
		mh.arr = nil
		return val
	}

	mh.arr[0] = mh.arr[mh.size-1]
	i := 0
	left := 1
	right := 2
	for (left <= mh.size-1 && mh.arr[i] > mh.arr[left]) || (right <= mh.size-1 && mh.arr[i] > mh.arr[right]) {
		if mh.arr[left] < mh.arr[right] {
			mh.swap(&mh.arr, i, left)
			i = left
		} else {
			mh.swap(&mh.arr, i, right)
			i = right
		}
		left = i*2 + 1
		right = i*2 + 2
	}
	mh.size--
	mh.arr = mh.arr[:mh.size]
	return val
}

func (mh *MinHeap) swap(arr *[]int, x int, y int) {
	t := (*arr)[x]
	(*arr)[x] = (*arr)[y]
	(*arr)[y] = t
}

func main() {
	heap := &MinHeap{}
	assert(0, heap.size)
	assert(0, heap.Min())
	assert(0, heap.ExtractMin())
	heap.Insert(10)
	assert(10, heap.Min())
	assert(10, heap.ExtractMin())
	assert(0, heap.Min())

	heap.Insert(6)
	heap.Insert(3)
	heap.Insert(65)
	heap.Insert(30)
	heap.Insert(50)
	heap.Insert(4)
	heap.Insert(100)
	heap.Insert(2)
	assert(2, heap.Min())
	assert(2, heap.ExtractMin())
	assert(3, heap.Min())
	assert(3, heap.ExtractMin())
	assert(4, heap.Min())
	assert(4, heap.ExtractMin())
	assert(6, heap.Min())
	assert(6, heap.ExtractMin())
	assert(30, heap.Min())
	assert(30, heap.ExtractMin())
	assert(50, heap.Min())
	assert(50, heap.ExtractMin())
	assert(65, heap.Min())
	assert(65, heap.ExtractMin())
	assert(100, heap.Min())
	assert(100, heap.ExtractMin())
	assert(0, heap.size)
}

func assert(expected, actual interface{}) {
	if expected != actual {
		log.Panicf("%s != %s", expected, actual)
	}
}