Heap(堆)

堆的特性（按最大堆说明）

1. 二叉树
2. 完全二叉树，还不是满二叉树
3. 节点的data值不小于子节点
4. 各子树仍然是最大堆
5. 树的节点存放在数组中

因为树的高度为log2(n)，所以：
插入时间复杂度：O(log2(n))
删除时间复杂度：O(log2(n))
堆的创建时间复杂度：
自顶向下建堆：O(nlog2(n))相当于对n个节点进行插入操作
自底向上建堆：O(n)，直接对堆进行调整

需要关注的指标：
树在数组中的处理方式，i为节点的下标值(0 ≤ i ≤ n-1)，n为节点个数

1. 父节点为(i-1)/2 (i ≠ 0)，i=0则为根节点
2. 左子节点为2i+1 (2i+1 ≤ n-1)，若不满足则无左子节点
3. 右子节点为2i+2 (2i+2 ≤ n-1)，若不满足则无右子节点

注意事项：
最大堆无法判断第几大的元素，只能获得第一大的元素

创建堆时：

1. 将节点按层序方式写入二叉树中
2. 找到最后的叶子节点
3. 根据叶子节点找到父节点
4. 父节点和两个子节点进行比较，看是否需要和某个子节点交换
5. 交换后仍需递归和下层子节点比较，直到没有节点需要交换(叶子节点或满足最大堆要求)

节点数为n，那么父节点i从(n/2)-1开始整理堆
func Heapify() {
    for i := n/2 - 1; i >= 0; i-- {
        h.Down(i, n)
    }
}
func (h *HeapInt) Down(i, n int) {
    //这是初始化
    for {
        left := 2*i + 1
        if left >= n || left < 0 {
            break
        }
        j := left
        if right := left + 1; right < n && h.Less(left, right) {
            j = right
        }
        if !h.Less(i, j) {
            break
        }
        h.Swap(i, j)
        i = j
    }
    return
}

插入时：

1. 将节点放到最后
2. 重新排列堆

我们需要进行siftUp操作：

• 将当前节点值与其父节点比较：
  • 如果节点已经为根节点，siftUp完成
  • 如果父节点大于当前节点，siftUp完成；
  • 如果父节点小于当前节点，交换两个节点。
• 更新当前节点。重复siftUp。

删除时（一般堆的作用就是用来删除最大值的，不会随便选择节点删除）：

1. 删除根节点
2. 将最后一个节点换到根节点
3. 重新排列堆

开始进行siftDown操作：

• 将当前节点（首次为根节点）与左右孩子中较大的节点进行比较；
  • 如果当前节点为叶子节点，siftDown完成；
  • 如果大于较大值，则已经符合最大堆的性质，siftDown完成；
  • 如果小于较大值，则与较大值进行交换
• 更新当前节点，再次进行siftDown操作。