package main

import "fmt"

// 堆节点
type Node struct {
	Value int
}

// 使用数组实现二叉堆
type Heap struct {
	Tree []*Node
}

// 定义获取父节点下标
func (h *Heap) Parent(i int) int {
	if i == 0 {
		return -1
	}
	return (i - 1) / 2
}

// 定义获取左右子节点下标
func (h *Heap) Left(i int) int {
	left := i * 2 + 1
	if left > len(h.Tree) {
		return -1
	}
	return left
}

func (h *Heap) Right(i int) int {
	right := i * 2 + 2
	if right > len(h.Tree) {
		return -1
	}
	return right
}

// 通过下标交换两元素
func (h *Heap) Swap(i, j int) {
	if i >= len(h.Tree) || j >= len(h.Tree) {
		return
	}

	h.Tree[i], h.Tree[j] = h.Tree[j], h.Tree[i]
}

// 定义比较函数
func (h *Heap) Less(i, j int) bool {
	// 这里定义的逻辑是按照小顶堆定义的，将最小的元素放在堆顶
	return h.Tree[i].Value < h.Tree[j].Value
}

// 上浮，在插入节点后使用。
// 调用前需要先插入数据。
func (h *Heap) Swim() {
	var parent, cur int
	// 取末尾上浮
	cur = len(h.Tree) - 1
	for {
		parent = h.Parent(cur)
		// 通过Less函数比较当前节点与父节点的值，决定是否交换。
		if parent == -1 || !h.Less(cur, parent) {
			break
		}

		h.Swap(cur, parent)
		cur = parent
	}
}

// 下沉，在删除节点时使用。
// 调用前需先将末尾节点与堆顶交换，然后通过Less函数比较下沉堆顶节点。
func (h *Heap) Sink() {
	var l, r, target, cur, tail int
	cur = 0
	// 末尾节点下标，末尾节点不参与比较
	tail = len(h.Tree) - 1
	for {
		l, r = h.Left(cur), h.Right(cur)
		target = l
		// 由于二叉堆是完全二叉树，因此可以保证，当左子树不存在是，那么右子树也必定不存在
		// 即当前节点为叶子节点，可以退出下沉操作
		if l == -1 || l >= tail {
			break
		}
		if r != -1 && r < tail && h.Less(r, l) {
			// 当r比l更满足要求（Less函数）时，替换r
			target = r
		}
		// 当target比cur更满足需求（Less函数）时，表示需要下沉，反之退出循环
		if h.Less(target, cur) {
			h.Swap(target, cur)
			cur = target
		} else {
			break
		}
	}
}

// 插入数据
func (h *Heap) Push(value int) {
	// 插入时需要将节点放置树的末尾，然后让其上浮
	h.Tree = append(h.Tree, &Node{Value: value})
	h.Swim()
}

// 弹出数据
func (h *Heap) Pop() *Node {
	root, tail := 0, len(h.Tree) - 1
	h.Swap(root, tail)
	h.Sink()
	// 末尾节点即为需要出栈的元素
	n := h.Tree[tail]
	// 出栈后需要删除末尾节点
	h.Tree = h.Tree[:tail]
	return n
}

func main() {
	h := &Heap{Tree: make([]*Node, 0)}

	h.Push(10)
	h.Push(9)
	h.Push(7)
	h.Push(6)
	h.Push(6)
	h.Push(4)
	h.Push(8)

	for len(h.Tree) != 0 {
		fmt.Printf("%d ", h.Pop().Value)
	}
	fmt.Println()
}