今天记录下堆的相关知识，先上定义（来自维基百科）。

堆（Heap）

堆（Heap）通常都是表示二叉堆（binary heap）是一种特别的完全二叉树完全二叉树：除最后一层其他层的节点都是满的，最后一层从左往右填充，始于 J. W. J. Williams 在 1964 年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。为什么会出现个完全二叉树的定义呢？因为使用数组表示的二叉树按序填充的结果正好是一颗完全二叉树。那数组怎么表示二叉树呢？😕

当前节点的左孩子索引 = 当前节点索引 * 2 + 1

当前节点的右孩子索引 = 当前节点索引 * 2 + 2

这么描述可能有点抽象，手画一个二叉树，带入索引计算一下你就会和我一样说一声：妙啊 👏。就跟并查集一样，最优雅的数据结构往往有着最简单的结构设计。这可能就是计算机科学的艺术吧。说完完全二叉树，回到堆的定义：若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。若母节点的值恒小于等于子节点的值，此堆称为小根堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为大根堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

可以看出，堆是只关心当前节点与其左右子节点的关系的，至于左右节点的大小关系是不关心的，因此，堆是不适合用来做搜索的。根据堆的特性，很容易发现：堆最有价值的是根节点是当前堆集合的极值，因此非常适合用来处理优先队列或者 top-N 的问题。

算法模板

1
2
3
4
5
6
class MinHeap {
    constructor() {
        // 二叉堆是用数组实现的
        this.heap = []
    }
}

下面的代码都是小根堆的实现

insert (向堆中插入一个新元素)

插入操作是向堆中插入一个元素，并重新使堆合法。具体怎么做呢？

  1. 先把值插入数组尾部
  2. 该元素与其父节点比较，更适合当极值的往上冒小根堆就是较小值，大根堆就是较大值
  3. 如果 2. 步骤发生了交换，则把交换后的节点重新进行 2. 的操作（直到根节点）

根据堆使用数组表示二叉树的原理，反推可以得出：

当前节点的父节点的索引 = Math.floor((当前节点的索引 - 1) / 2) // Math.floor 向下取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 向堆中插入一个新元素
 * @param num 插入值
 */
insert(num) {
    const siftUp = (i) => {
        const fi = Math.floor((i - 1) / 2) // 父节点索引
        if (fi > -1 && this.heap[fi] > this.heap[i]) { // 当前节点比它的父节点更适合当极值（较小值）
            [this.heap[fi], this.heap[i]] = [this.heap[i], this.heap[fi]]
            siftUp(fi) // 递归
        }
    }
    // 1. 先把值插入数组尾部
    this.heap.push(num)
    // 2. 将新元素提升使其符合堆的性质
    siftUp(this.heap.length - 1)
}

siftUp 其实就是将新元素提升使其符合堆的性质，可见递归次数最差就是树的深度，因此时间复杂度为 O(logn)O(log n)，因此插入操作的时间复杂度也是O(logn)O(log n)。

delete (删除堆顶元素)

围绕着根节点是当前堆集合的极值这一特征，堆的删除的意思是：删除当前堆的极值(也就是根节点)，并重新使这个堆合法化heapify (堆化)。由于使用的数组实现的堆，因此第一步需要选择一个新的节点成为根节点，也就是末尾节点选别的节点很有可能会破环树的结构，造成不必要的开销。

  1. 把首节点也就是根节点与尾节点互换，删除尾节点（也就是原根节点）
  2. 首节点与左右子节点比较，更适合当极值的往上冒小根堆就是较小值，大根堆就是较大值
  3. 如果 2. 步骤发生了交换，则把交换后的节点重新进行 2. 的操作（直到越界）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 删除堆顶元素
 */
delete() {
    const siftDown = (i) => {
        // 检查子节点是否越界，这里只比较左节点（左节点都越界了，右节点不用看了）
        if (2 * i + 1 < this.heap.length) {
            const lc = this.heap[2 * i + 1]
            const rc = this.heap[2 * i + 2] ?? Infinity // 右节点不存在时给个最大值，保证它不会提升
            if (lc < rc) {
                if (lc < this.heap[i]) { // 左节点比当前节点更适合当极值（较小值）
                    [this.heap[i], this.heap[2 * i + 1]] = [this.heap[2 * i + 1], this.heap[i]]
                    siftDown(2 * i + 1) // 递归替换的子节点
                }
            } else {
                if (rc < this.heap[i]) { // 右节点比当前节点更适合当极值（较小值）
                    [this.heap[i], this.heap[2 * i + 2]] = [this.heap[2 * i + 2], this.heap[i]]
                    siftDown(2 * i + 2) // 递归替换的子节点
                }
            }
        }
    }
    // 1. 先首尾互换
    [this.heap[0], this.heap[this.heap.length - 1]] = [this.heap[this.heap.length - 1], this.heap[0]]
    // 2. 删除尾节点（原根节点）
    const res = this.heap.pop()
    // 3. 将根元素下沉使其符合堆的性质
    siftDown(0)
    return res
}

siftDown 其实就是将元素下沉使其符合堆的性质，可见递归次数最差就是树的深度，因此时间复杂度为 O(logn)O(log n)，因此删除操作的时间复杂度也是O(logn)O(log n)。

build (建立堆)

  1. 新建堆 (自顶向下)
    由于堆是使用数组实现的，因此，如何使一个数组快速转为堆的问题不可避免的出现了。借助上面已经实现的算法，第一反应就是，新建一个堆，把数组的每个元素依次插入到堆中。easy peasy🤟🤟。时间复杂度很容易算出来: n 次插入操作nO(logn)nO(log n)。由于随着节点的增加，树是一层一层的从上往下构建出来的，因此叫自顶向下的方向构建的。
  2. Floyd 建堆算法（自底向上）
    采用罗伯特·弗洛伊德提出的较快方式建立堆，方法是这样的，倒序遍历也就是层序的从右往左，使得每个节点都满足堆的特性。这样保证了每个节点在遍历时，其子节点是满足堆特性的，这样使用该节点去 siftDown也就是根节点去左右子树（左右子树已经满足堆特性）中找一个最合适的极值才是有效的。算法复杂度可以想象一下，最下层是 0 次叶子节点无需siftDown，往上一层是最差 1 次，一直到根节点就是树的高度 h，然后每层的节点是20−2h2^0 - 2^h，累加后时间复杂度为O(n)O(n) 。