堆的结构，堆的创建，节点添加与删除

题目来源：好未来

答案：

堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置.

如下图这是一个最大堆，，因为每一个父节点的值都比其子节点要大。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()
}