Golang Heaps

max_heap.go

package main

import "container/heap"

var _ heap.Interface = (*MaxHeap)(nil)

type MaxHeap []int

func (h *MaxHeap) Len() int {
	return len(*h)
}

func (h *MaxHeap) Less(i int, j int) bool {
	return (*h)[i] > (*h)[j]
}

func (h *MaxHeap) Swap(i int, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *MaxHeap) Push(x any) {
	v := x.(int)
	*h = append(*h, v)
}

func (h *MaxHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *MaxHeap) Peek() any {
	if h.Len() == 0 {
		return nil
	}

	return (*h)[0]
}

min_heap.go

package main

import "container/heap"

var _ heap.Interface = (*MinHeap)(nil)

type MinHeap []int

func (h *MinHeap) Len() int {
	return len(*h)
}

func (h *MinHeap) Less(i int, j int) bool {
	return (*h)[i] < (*h)[j]
}

func (h *MinHeap) Swap(i int, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *MinHeap) Push(x any) {
	v := x.(int)
	*h = append(*h, v)
}

func (h *MinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *MinHeap) Peek() any {
	if h.Len() == 0 {
		return nil
	}

	return (*h)[0]
}

min_heap_without_pkg.go

package main

type MinHeapInt struct {
	arr []int
}

func NewMinHeapInt(v []int) *MinHeapInt {
	if v == nil {
		v = make([]int, 0)
	}

	h := &MinHeapInt{
		arr: v,
	}

	last_non_leaf_idx := h.parentIdx(h.Len() - 1)

	for i := last_non_leaf_idx; i >= 0; i-- {
		h.down(i)
	}

	return h
}

func (h *MinHeapInt) Len() int {
	return len(h.arr)
}

func (h *MinHeapInt) Push(v int) {
	h.arr = append(h.arr, v)
	h.up(h.Len() - 1)
}

func (h *MinHeapInt) Peek() int {
	if h.Len() == 0 {
		return -1
	}
	return h.arr[0]
}

func (h *MinHeapInt) Pop() int {
	if h.Len() == 0 {
		return -1
	}

	h.swap(0, h.Len()-1)
	x := h.arr[h.Len()-1]
	h.arr = h.arr[0 : h.Len()-1]
	h.down(0)
	return x
}

func (h *MinHeapInt) swap(i, j int) {
	h.arr[i], h.arr[j] = h.arr[j], h.arr[i]
}

func (*MinHeapInt) parentIdx(idx int) int {
	if idx == 0 {
		return -1
	}
	return (idx - 1) / 2
}

func (h *MinHeapInt) childsIdx(idx int) (int, int) {
	left := (2 * idx) + 1
	right := (2 * idx) + 2
	if left >= h.Len() {
		left = -1
	}
	if right >= h.Len() {
		right = -1
	}
	return left, right
}

func (h *MinHeapInt) up(child int) {
	for child != 0 {
		parent := h.parentIdx(child)
		if h.arr[parent] <= h.arr[child] {
			break
		}
		h.swap(parent, child)
		child = parent
	}
}

func (h *MinHeapInt) down(parent int) {
	n := h.Len()

	for ((2 * parent) + 1) < n {
		child := h.minChildIdx(parent)
		if child == parent {
			break
		}
		h.swap(parent, child)
		parent = child
	}
}

func (h *MinHeapInt) minChildIdx(p int) int {
	l, r := h.childsIdx(p)

	if l == -1 && r == -1 {
		return p
	}

	if r == -1 {
		if h.arr[p] <= h.arr[l] {
			return p
		} else {
			return l
		}
	}

	if h.arr[p] <= h.arr[l] && h.arr[p] <= h.arr[r] {
		return p
	}
	if h.arr[l] < h.arr[r] {
		return l
	}
	return r
}