golang priority queue implementation
package main import ( "fmt" "golang.org/x/exp/constraints" ) type MinHeap[T constraints.Ordered] struct { Items []T } func NewMinHeap[T constraints.Ordered]() *MinHeap[T] { return &MinHeap[T]{} } func getLeftChildIndex(index int) int { return index*2 + 1 } func getRightChildIndex(index int) int { return index*2 + 2 } func getParentIndex(index int) int { return (index - 1) / 2 } func (this *MinHeap[T]) hasLeftChild(index int) bool { return getLeftChildIndex(index) < len(this.Items) } func (this *MinHeap[T]) hasRightChild(index int) bool { return getRightChildIndex(index) < len(this.Items) } func (this *MinHeap[T]) hasParent(index int) bool { return getParentIndex(index) >= 0 } func (this *MinHeap[T]) leftChild(index int) T { return this.Items[getLeftChildIndex(index)] } func (this *MinHeap[T]) rightChild(index int) T { return this.Items[getRightChildIndex(index)] } func (this *MinHeap[T]) parent(index int) T { return this.Items[getParentIndex(index)] } func (this *MinHeap[T]) swap(indexOne, indexTwo int) { this.Items[indexOne], this.Items[indexTwo] = this.Items[indexTwo], this.Items[indexOne] } func (this *MinHeap[T]) Peek() T { if len(this.Items) == 0 { panic("No items to peek") } return this.Items[0] } func (this *MinHeap[T]) Poll() T { if len(this.Items) == 0 { panic("No items to Poll") } item := this.Items[0] this.Items[0] = this.Items[len(this.Items)-1] this.Items = this.Items[:len(this.Items)-1] this.HeapifyDown() return item } func (this *MinHeap[T]) Add(item T) { this.Items = append(this.Items, item) this.HeapifyUp() } func (this *MinHeap[T]) HeapifyUp() { index := len(this.Items) - 1 for this.hasParent(index) && this.parent(index) > this.Items[index] { this.swap(getParentIndex(index), index) index = getParentIndex(index) } } func (this *MinHeap[T]) HeapifyDown() { index := 0 for this.hasLeftChild(index) { smallerChildIndex := getLeftChildIndex(index) if this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index) { smallerChildIndex = getRightChildIndex(index) } if this.Items[index] < this.Items[smallerChildIndex] { break } else { this.swap(index, smallerChildIndex) index = smallerChildIndex } } } func main() { mm := NewMinHeap[int]() mm.Add(10) mm.Add(3) mm.Add(1) mm.Add(2) mm.Poll() fmt.Println(mm.Peek()) }
