堆

定义与性质

堆是一种具有特殊性质的树，特殊在于：

它是一棵完全二叉树（除了最后一层的节点，其他节点都有两个子节点。
它的任意一个节点的值都比它的子节点（若存在子节点）的值大或小（据此分为最大堆和最小堆）。

堆有一个别名：优先队列（为何详见堆的应用）。

一个最大堆如图所示：

接下来讲解堆的相关内容均以最大堆为例。
观察可以发现，堆还有一些其他性质：

第 i 层的节点可能比第 i-1 层的大，但一定比第 i-2 层的小（记住它，等下理解堆的两个重要操作：上推和下拉时，遇到问题就想想它）。

堆的实现和基本操作
一般堆的基本操作包括：
建堆。有交换建堆法和插入建堆法。
删除一个元素。
插入一个元素。

用数组能够很好的实现堆，因为通过数组的下标可以很快地找到节点的父子关系，以最大堆为例：

图1

假设某个节点在数组中下标为 i，那么它的两个子节点的下标分别为 2*i+1 和 2*i+2（如果有的话）。

插入、删除和建堆

为什么不先讲如何建堆呢？
因为堆有两个非常重要的操作：上推和下拉。
上推：用于插入元素时，维护堆的性质。
下拉：用于删除元素时，维护堆的性质。
建堆就是通过这两个方法实现的！

上推实现插入和建堆

以图 1 为例，假如现在插入一个元素 9，如何通过上推维护堆的性质呢？

上推的思想：将插入的元素与它的父节点比较，若小于等于，则说明新元素已处于正确的位置；否则将它与父节点交换。交换后可能导致破坏了它所处的子树的堆性质，继续采用上述方法比较，直至它处于正确位置或到达根节点。

例子比较特殊，其实大多数时候不需要到达根节点就可以找到合适的位置。
由此可以得到启发，**插入建堆法**：如果把元素依次插入，插入后使用上推维护堆的性质，就可以构建堆了！
但是这种方法的时间代价是堆 - 图4 的，不够堆 - 图5 的交换建堆法好。

下拉实现删除和建堆

以图 1 为例，如何删除元素 8 呢，删除后如何维护堆的性质呢？

下拉的思想：将要删除的元素和末尾元素 x 交换，然后 x 与 x 的子节点比较，若 x 不是最大的，则与较大的子节点交换。交换后可能导致破坏了它所处的子树的堆性质，继续采用上述方法比较，直至它处于正确位置或到达底层。

由此又获得启发，**交换建堆法**：对于任意一个数组，依次对末尾元素到首元素采用下拉法，即可构建堆！

顺序不能错，一定是从末尾元素到首元素。
按顺序的情况下，可以不处理叶子节点，因为叶子节点已经无法下拉，这可以大大提高性能，因为在一棵完全二叉树中，叶子节点是所有节点的一半以上。

堆的遍历和查找

用数组实现堆，有什么好遍历和查找的，直接扫描一遍就行了= =！
堆的性质并不能给查找带来性能提升！

代码实现

package main
import (
    "fmt"
)
func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    buildHeap(nums)
    fmt.Println(nums)
}
// 上推
func pushup(nums []int, valIdx int) {
    // val 已经推到根节点
    if valIdx == 0 {
        return
    }
    rootIdx := int((valIdx - 1) / 2)
    // val 已经推到正确位置
    if nums[valIdx] <= nums[rootIdx] {
        return
    }
    // val 还没推到正确位置，继续往上推
    nums[rootIdx], nums[valIdx] = nums[valIdx], nums[rootIdx]
    // 由于发生上推，可能破坏局部最大堆性质
    // 所以要尝试继续往上推
    pushup(nums, rootIdx)
}
// 插入
// 借助上推实现
func insert(nums []int, val int) []int {
    nums = append(nums, val)
    pushup(nums, len(nums)-1)
    return nums
}
// 下拉
func pulldowm(nums []int, i int, size int) {
    largest, left, right := i, 2*i+1, 2*i+2
    if left < size && nums[left] > nums[largest] {
        largest = left
    }
    if right < size && nums[right] > nums[largest] {
        largest = right
    }
    if largest != i {
        nums[i], nums[largest] = nums[largest], nums[i]
        pulldowm(nums, largest, size)
    }
}
// 交换建堆法
// 借助下拉实现
func buildHeap(nums []int) {
    for i := int(len(nums) / 2); i >= 0; i-- {
        pulldowm(nums, i, len(nums))
    }
}

代码中采用了交换建堆法，有兴趣的朋友可以自己试试插入建堆法（毕竟 insert() 都在那了= =）。
代码中没有写删除操作，因为删除涉及细节很多。比如说是否允许堆中含有同值元素？如果允许，删除法给出的参数就不能是值，而应该是数组下标。

堆的应用

堆排序

容易想到，如果我们对一个最大堆每次删除堆顶元素，删完整个堆就可以获得一个升序序列。
代码实现如下：

func heapSort(nums []int) {
    buildHeap(nums)
    last := len(nums) - 1                    // 尾元素指针
    for i := last; i >= 0; i-- {            
        nums[0], nums[i] = nums[i], nums[0]    // 与末尾元素交换
        pulldowm(nums, 0, last)                // 下拉维持堆性质
        last--                                // 减少一个元素
    }
}

细节：

删除并不是真的删除，而是通过一个尾指针 last 控制参与形成堆的元素个数，从而使得被移到数组后面的元素不再参与下拉操作。

正因为如此，每次删除堆顶元素后，都可以重新形成一个新的堆，因此堆又被称为优先队列，即优先权最高的最先出队。

堆

堆