Created
May 9, 2021 21:03
-
-
Save kiambogo/2425b2cd98e6cd3a53750ea9f7786e5b to your computer and use it in GitHub Desktop.
Go Min Heap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment