堆

二叉堆是一棵完全二叉树，通常用数组存储。大根堆满足任一父结点不小于孩子，根保存最大值；小根堆则相反，根保存最小值。堆适合持续插入元素并快速取得当前最值。

1. 数组表示与堆性质

下面采用从 1 开始的数组下标：结点 i 的父结点为 i / 2，左孩子为 2 * i，右孩子为 2 * i + 1。完全二叉树没有空洞，因此不需要指针。

// heap[1..n] 为 1 下标大根堆
int parent(int i) { return i / 2; }
int left(int i)   { return i * 2; }
int right(int i)  { return i * 2 + 1; }

2. 上浮与下沉

插入新元素后，它可能比父结点大，需要不断上浮。删除堆顶时，把最后一个元素移到根，再与较大的孩子交换并不断下沉。这两个操作只沿一条根到叶的路径移动。

void siftDown(vector<int>& heap, int i, int n) {
    while (true) {
        int l = i * 2, r = l + 1, largest = i;
        if (l <= n && heap[l] > heap[largest]) largest = l;
        if (r <= n && heap[r] > heap[largest]) largest = r;
        if (largest == i) break;
        swap(heap[i], heap[largest]);
        i = largest;
    }
}

void push(vector<int>& heap, int x) {
    heap.push_back(x);
    for (int i = (int)heap.size() - 1; i > 1 && heap[i] > heap[i / 2]; i /= 2)
        swap(heap[i], heap[i / 2]);
}

使用上述 push 前，可先放一个无意义的占位元素，使真正数据从 heap[1] 开始。

3. 建堆与堆排序

对无序数组，不必逐个插入。最后一个非叶结点是 n / 2，从它向前逐个下沉即可在 O(n) 时间建成大根堆。随后反复把堆顶与末尾交换、缩小堆范围并下沉根，便得到从小到大的堆排序结果。

for (int i = n / 2; i >= 1; --i) siftDown(heap, i, n); // 建大根堆
for (int end = n; end > 1; --end) {
    swap(heap[1], heap[end]);
    siftDown(heap, 1, end - 1);
}

4. C++ 优先队列

实际编程中通常直接使用 priority_queue。默认是大根堆；指定 greater<int> 后是小根堆，适用于动态取最小值、Top-K 和 Dijkstra 等场景。

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

minHeap.push(5); minHeap.push(2); minHeap.push(7);
int smallest = minHeap.top(); // 2
minHeap.pop();

5. 复杂度与限制

查看堆顶为 O(1)；插入和删除堆顶为 O(log n)；自底向上建堆为 O(n)；堆排序为 O(n log n) 且可原地完成。堆只保证堆顶是最值，不能像有序数组那样快速查找任意元素，也不能直接按完整有序顺序遍历。