最小堆-构造解释

概念
- 是一颗完全二叉树
- 结构特性
  - 每一层都有左侧和右侧子节点(除最后一层)
  - 最后一层的叶节点尽可能都是左侧子节点
- 堆特性
  - 堆节点的左边或右边，所有节点的值都比它大
使用数组heap表示
- 若一个堆节点位于索引 index，那么
- 左侧子节点位于索引 2 * index + 1
- 右侧子节点位于索引 2 * index + 2
- 父节点位于索引 Math.floor((index - 1) / 2)

插入

把value放到最后，位置就是this.heap.length - 1
指定这个位置往上冒，完成siftUp，即可维持最小堆特性

insert(value) {
    if (value === null) return false;
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
    return true;
}

往上冒
- 计算出它的父母，定义为parent
- 如果当前index还没到顶部0，并且parent处值比当前节点大，代表需要交换两节点的值
  - 交换完成后，index应该重新设置到parent处
  - 这时候就可以重新计算新的parent，等待进入下一次循环，继续往上冒
```
siftUp(index) {
    let parent = Math.floor((index - 1) / 2);
    while (index > 0 && this.heap[parent] > this.heap[index]) {
        [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
        index = parent;
        parent = Math.floor((index - 1) / 2);
    }
}
```
弹出
- 如果为空则返回undefined
- 如果只有1个也直接返回，不过要记得是shift弹出，不能直接取
- 先把0号位置代表的最小值暂存起来
  - 然后把末尾弹出，放到0号位置
  - 指定0号位置向下沉，即可维持最小堆特性
- 最后返回存起来的值
```
extract() {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.shift();
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return minValue;
}
```
向下沉
- 计算出子节点中比它小最多的那一个，定义为child
  - 这里为了比较，child初始是index当前节点
  - 先与left比较，若left合法，并且比child处值要小，代表有机会
  - 然后与right比较，若right合法，并且比child处值要小，代表也有机会
  - 【注意】这里比较时是对child比较，本质是贪心法，两次下来总是能找到最小的那个child
- 当child不等于index时，证明找到一个更小的子节点，代表要交换两节点的值
  - 交换完成后，应该让child成为新的关注节点，让它继续尝试往下沉
- 沉到底，就会出现left和right都没有，也就是超过heap边界，就会自动返回
```
siftDown(index) {
    let child = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    if (left < this.heap.length && this.heap[left] < this.heap[child]) {
        child = left;
    }
    if (right < this.heap.length && this.heap[right] < this.heap[child]) {
        child = right;
    }
    if (child !== index) {
        [this.heap[child], this.heap[index]] = [this.heap[index], this.heap[child]];
        this.siftDown(child);
    }
}
```

Keyboard shortcuts

最小堆-构造解释