Heap
堆
树与堆核心时间 插入 / 弹出 O(log n)空间 O(n)
完全二叉树，父结点总不小于（或小于）孩子。数组即可表示，堆顶永远是最值。
动画
插入 4 到堆尾
1 / 13
- 当前
讲解
优先队列、堆排序、Top-K、Dijkstra 的待处理集合。
- 01下标 i 的左孩子 2i+1、右孩子 2i+2、父结点 ⌊(i-1)/2⌋。
- 02插入放到末尾再上浮，直到堆序恢复。
- 03弹出堆顶：与末尾交换，缩小堆，再下沉。
- 04建堆可自底向上 heapify，O(n)。
易错点
- 分清大根堆 / 小根堆，比错方向会全乱。
- 数组实现时注意下标从 0 还是 1 开始。
代码
function siftUp(a, i) {
while (i > class="text-accent">0) {
const p = (i - class="text-accent">1) >> class="text-accent">1;
if (a[i] <= a[p]) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
function push(a, v) { a.push(v); siftUp(a, a.length - class="text-accent">1); }