题目序号：3393
题目来源：好未来
频次：1
答案：村雨
堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置.
如下图这是一个最大堆，，因为每一个父节点的值都比其子节点要大。10 比 7 和 2 都大。7 比 5 和 1都大。
根据这一属性，那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆，根节点中的元素总是树中的最小值。堆属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到“最重要”的元素。
在Go中，堆结构的实现依赖于使用者对于Heap接口进行实现，更加灵活，但也需要额外的工作量。Go 提供了container/heap这个包来实现堆的操作。
堆中元素的类型需要实现 heap.Interface 这个接口:
type Interface interface {
sort.Interface
Push(x interface{}) // 将x添加至元素Len()的位置
Pop() interface{} // 移除并且返回元素Len()-1
}其中 sort.Interface 包括 Len(), Less, Swap 方法
以一个int类型的堆来举例，在使用堆之前，我们需要定义堆的底层数组：type IntHeap []int
然后，我们需要实现heap.Interface接口的五个函数：
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}需要注意的是，在实现Push()和Pop()的时候，需要使用指针接收，而不能简单的使用对象。因为Go语言结构体传参默认是传值，而在修改切片长度的时候有可能导致切片的引用发生改变，所以需要使用指针接收。
然后，我们就可以使用这个堆了：
func Example_intHeap() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("堆顶元素: %d
", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
// 输出:
// 堆顶元素: 1
// 1 2 3 5
}关于节点的增加和删除
可参考这三个内置函数：Push():
Push()将元素x插入到堆中。
Push()的时间复杂度是O(log n)，n为堆中的元素个数。
func Push(h Interface, x interface{}) {
h.Push(x)
up(h, h.Len()-1)
}从源码可以看出，实际的插入步骤是先调用heap.Interface接口的Push()函数将待插入的元素x放到堆中的最后一个位置，然后对其进行上浮操作。
Pop():
Pop()从堆中移除并返回最小元素（根据Less）。也就是堆顶元素。
Pop()的时间复杂度是O(log n)，n为堆中的元素个数。
Pop()等价于Remove(h, 0)。
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}从源码可以看出，实际的弹出步骤是将第一个元素与最后一个元素进行互换，然后对一个元素进行下沉，最后移除并返回最后一个元素。
Remove:
Remove()从堆中移除并返回第i个元素。
Remove()的时间复杂度是O(log n)，n为堆中的元素个数。
func Remove(h Interface, i int) interface{} {
n := h.Len() - 1
if n != i {
h.Swap(i, n)
if !down(h, i, n) {
up(h, i)
}
}
return h.Pop()
}