package heap

import "gitee.com/guuzaa/algorithm/constraints"

type MinHeap[T constraints.Ordered] struct {
	nums   []T
	length int
}

func NewMinHeap[T constraints.Ordered]() MinHeap[T] {
	return MinHeap[T]{make([]T, 0), 0}
}

func (h *MinHeap[T]) Push(val T) {
	h.nums = append(h.nums, val)
	h.length++

	lastParent := parent(h.length)
	for i := lastParent; i >= 0; i-- {
		moveDown(h.nums, i)
	}
}

func (h *MinHeap[T]) Pop() T {
	val := h.nums[0]
	h.length--
	h.nums[0] = h.nums[h.length]
	h.nums = h.nums[:h.length]

	moveDown(h.nums, 0)

	return val
}

func (h *MinHeap[T]) Len() int {
	return h.length
}

func (h *MinHeap[T]) IsEmpty() bool {
	return h.length == 0
}

func moveDown[T constraints.Ordered](nums []T, parent int) {
	last := len(nums) - 1
	for {
		left, right := leftChild(parent), rightChild(parent)
		if left > last {
			break
		}

		child := left
		if right <= last && nums[right] < nums[child] {
			child = right
		}

		// ! Note
		if nums[parent] > nums[child] {
			nums[parent], nums[child] = nums[child], nums[parent]
		}

		parent = child
	}
}

func parent(child int) int {
	return child / 2
}

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

func rightChild(parent int) int {
	return (parent + 1) * 2
}