二叉堆
入门二叉堆把树结构压缩进数组，用父子关系维护局部有序。
// 算法讲解
二叉堆
默认按最大堆展示堆顶和下沉过程。
待机
速度 中
待机 ⌨1void siftDown(vector<int>& heap, int i) {
2 int n = heap.size();
3 while (true) {
4 int left = i * 2 + 1;
5 int right = i * 2 + 2;
6 int largest = i;
7 if (left < n && heap[left] > heap[largest]) largest = left;
8 if (right < n && heap[right] > heap[largest]) largest = right;
9 if (largest == i) break;
10 swap(heap[i], heap[largest]);
11 i = largest;
12 }
13}
复杂度分析
时间 建堆 O(n), 插入/删除 O(log n)
空间 O(n)
最优 取顶 O(1)
最坏 调整 O(log n)
算法讲解
二叉堆通常用数组存储，索引 i 的左右孩子分别位于 2i 和 2i+1（或 2i+1、2i+2）的固定位置。
最大堆要求每个父节点都不小于孩子，最小堆则相反，因此堆顶始终是当前极值。
插入元素时通过上浮恢复堆序，删除堆顶时通过下沉恢复堆序。
它是理解堆排序、优先队列和很多贪心调度题的基础。