kiambogo · May 9, 2021 21:03 · May 9, 2021
diff --git a/min_heap.go b/min_heap.go
@@ -0,0 +1,112 @@
+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)
+	}
+}
No results found