fuzz

heap.go

type Heap struct {
	elements []int
}

func (h *Heap) Push(ele int) {
	h.elements = append(h.elements, ele)
	i := len(h.elements) - 1
	for ; h.elements[i] > h.elements[parent(i)]; i = parent(i) {
		h.swap(i, parent(i))
	}
}

func (h *Heap) Pop() (ele int) {
	ele = h.elements[0]
	h.elements[0] = h.elements[len(h.elements)-1]
	h.elements = h.elements[:len(h.elements)-1]
	h.rearrange(0)
	return
}

func (h *Heap) rearrange(i int) {
	largest := i
	left, right, size := leftChild(i), rightChild(i), len(h.elements)
	if left < size && h.elements[left] > h.elements[largest] {
		largest = left
	}
	if right < size && h.elements[right] > h.elements[largest] {
		largest = right
	}
	if largest != i {
		h.swap(i, largest)
		h.rearrange(largest)
	}
}

func (h *Heap) Build() {
	for i := len(h.elements) - 1; i >= 0; i-- {
		h.rearrange(i)
	}
}

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

func parent(i int) int {
	return (i - 1) / 2
}

func leftChild(i int) int {
	return 2*i + 1
}

func rightChild(i int) int {
	return 2*i + 2
}