堆一种特殊的树，满足下面两个条件：
- 堆总是一棵完全二叉树。
- 堆中某个节点的值总是大于等于（小于等于）其所有子节点的值。如果是大于等于情况就称为大顶堆，小于等于情况就是小顶堆。
在Java语言中，我们可以直接使用容器PriorityQueue实现堆。
Golang也存在类似的实现方式，但本文先介绍一下手动实现，再介绍如何使用golang提供的接口实现。
一、手撕代码实现
1.1、说明
由堆的性质可知，堆是一颗完全二叉树，因此，利用数组（切片）结构来存放堆最合适。
假设某结点数组下标为i（i>=1），该结点的子节点如果存在，则子节点的下标为2*i和2*i+1。为了使代码更加简洁，此处将堆顶元素的下标设置为1。
1.2、代码
type Myheap struct {
nums []int
}
//创建堆
func NewMyHeap() *Myheap {
return &Myheap{
nums: make([]int, 1),
}
}
func (this *Myheap) Push(val int) {
//将新添加的结点放置在最后
this.nums = append(this.nums, val)
pos := len(this.nums) - 1
//根据堆的规则，将该结点向上调整
for pos > 1 && this.nums[pos/2] > this.nums[pos] {
this.nums[pos/2], this.nums[pos] = this.nums[pos], this.nums[pos/2]
}
}
func (this *Myheap) Pop() (int, error) {
//判断堆中是否还存在结点
if len(this.nums) <= 1 {
return 0, errors.New("empty")
}
val := this.nums[1]
//将堆的根结点与最后一个结点交换
this.nums[1], this.nums[len(this.nums)-1] = this.nums[len(this.nums)-1], this.nums[1]
//删除最后一个结点（原根节点）
this.nums = this.nums[:len(this.nums)-1]
//将此时的根结点向下调整到正确的位置
if len(this.nums) > 1 {
this.adjustDown(1)
}
return val, nil
}
func (this *Myheap) adjustDown(pos int) {
length := len(this.nums) - 1
//此处规定下标从1开始，因此下标为0的位置可以用来暂时保存值
this.nums[0] = this.nums[pos]
//for循环为找子节点过程
for i := 2 * pos; i <= length; i *= 2 {
//找到更小的子节点
if i < length && this.nums[i] > this.nums[i+1] {
i++
}
//如果存在子节点小于需要调整的结点，则将子节点移动到父节点位置
if this.nums[0] > this.nums[i] {
this.nums[pos] = this.nums[i]
pos = i
}
}
//将结点放置在正确的位置
this.nums[pos] = this.nums[0]
}
//测试
func main() {
heap := NewMyHeap()
heap.Push(1)
heap.Push(4)
heap.Push(3)
heap.Push(2)
pop, _ := heap.Pop()
fmt.Println(pop) //1
pop, _ = heap.Pop()
fmt.Println(pop) //2
pop, _ = heap.Pop()
fmt.Println(pop) //3
pop, _ = heap.Pop()
fmt.Println(pop) //4
}
二、基于go提供的接口实现
2.1、说明
在Golang的container/heap包下面有堆的接口，只需要实现接口即可简单的实现二叉堆。
如下为该接口的代码，显然，实现heap接口的同时，得先实现sort接口。
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
go标准文档：
任何实现了本接口的类型都可以用于构建最小堆。最小堆可以通过
heap.Init建立，数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是：!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()注意：接口的Push和Pop方法是供heap包调用的，请使用
heap.Push和heap.Pop来向一个堆添加或者删除元素。
2.2、代码
type MyHeap []int
func (m MyHeap) Len() int {
return len(m)
}
//如果实现大顶堆，则需要调整一下Less函数
func (m MyHeap) Less(i, j int) bool {
if m[i] < m[j] {
return true
}
return false
}
func (m MyHeap) Swap(i, j int) {
m[i], m[j] = m[j], m[i]
}
func (m *MyHeap) Push(x any) {
*m = append(*m, x.(int))
}
func (m *MyHeap) Pop() any {
val := (*m)[len(*m)-1]
*m = (*m)[:len(*m)-1]
return val
}
func main() {
myHeap := MyHeap{3, 6, 2, 1, 4, 5}
heap.Init(&myHeap) //如果没有初始值，可以不需要使用此方法
heap.Push(&myHeap, 7)
fmt.Println(myHeap) //[1 3 2 6 4 5 7]
pop := heap.Pop(&myHeap)
fmt.Println(pop) //1
fmt.Println(myHeap) //[2 3 5 6 4 7]
}
/* 没有初始值
func main() {
myHeap := make(MyHeap, 0)
heap.Push(&myHeap, 7)
heap.Push(&myHeap, 2)
heap.Push(&myHeap, 3)
heap.Push(&myHeap, 8)
fmt.Println(myHeap) //[2 7 3 8]
pop := heap.Pop(&myHeap)
fmt.Println(pop) //2
fmt.Println(myHeap) //[3 7 8]
}
*/
