深入解析二叉堆的结构与操作

核心逻辑与数学原理

二叉堆本质上是一棵满足特定堆性质的完全二叉树。其核心逻辑在于利用数组的连续内存空间，通过下标的算术关系隐式维护树形拓扑结构，从而消除指针开销。

对于一棵以 $1$ 为根节点下标的完全二叉树，任意节点 $i$ 的拓扑几何关系满足：

左子节点下标：$2i$
右子节点下标：$2i + 1$
父节点下标：$\lfloor i/2 \rfloor$

以大根堆为例，其数学全序关系必须严格满足：

$$\forall i > 1, \quad \text{heap}[\lfloor i/2 \rfloor] \ge \text{heap}[i]$$

二叉堆的动态维护操作基于两种底层堆化机制，时间复杂度均为 $O(\log N)$：

向上堆化（Shift Up）：当在堆底插入新元素时，若该元素打破了堆性质，则将其沿父节点链条向上交换，直到满足全序关系。
向下堆化（Shift Down）：当弹出品质最高的堆顶元素时，将堆底末尾元素覆盖至堆顶，随后将该元素沿着左右子节点中较大者的路径向下交换，直到重新压制住子树。

状态设计与算法推导

手写二叉堆的状态极简，仅需一个一维静态数组 heap[] 和一个记录当前元素数量的计数器 sz。

1. push 操作（插入）与 Shift Up 推导

新元素置于 heap[++sz]。设当前考查下标为 $curr$：

判定条件：若 $curr > 1$ 且 $\text{heap}[curr] > \text{heap}[\lfloor curr/2 \rfloor]$。
转移状态：交换双方，令 $curr = \lfloor curr/2 \rfloor$，继续迭代。
终止条件：到达根节点（$curr = 1$）或当前节点不再大于其父节点。

2. pop 操作（删除）与 Shift Down 推导

释放堆顶，执行 heap[1] = heap[sz--]。设当前下沉下标为 $curr$：

判定条件：寻找其左子节点 $t = 2 \times curr$。若 $t \le sz$，说明存在左子节点。
兄弟对位：若 $t + 1 \le sz$ 且 $\text{heap}[t+1] > \text{heap}[t]$，说明右子节点更大，将目标指针修正为右子节点，即 $t = t + 1$。
下沉判定：若 $\text{heap}[t] > \text{heap}[curr]$，则交换 heap[curr] 与 heap[t]，令 $curr = t$，继续下沉。
终止条件：子节点下标 $t > sz$（触底）或当前节点已大于所有子节点。

C++ 核心模板代码 (NOI 风格)

const int MAXN = 100005;
int heap[MAXN], sz = 0;

void push(int val) {
    heap[++sz] = val; // 新元素置于堆底末尾
    int curr = sz;
    // 向上堆化：必须保证 curr > 1，避免越界访问 heap[0]
    while (curr > 1 && heap[curr] > heap[curr / 2]) {
        swap(heap[curr], heap[curr / 2]);
        curr /= 2; // 沿父节点路径上浮
    }
}

void pop() {
    if (sz == 0) return;
    heap[1] = heap[sz--]; // 堆底元素覆盖堆顶，同时将堆大小减一
    int curr = 1;
    // 向下堆化：只要存在左子节点就继续判定
    while ((curr * 2) <= sz) {
        int t = curr * 2; 
        // 关键边界检查：必须先确认 t + 1 <= sz，防止越界读取残留脏数据
        if (t + 1 <= sz && heap[t + 1] > heap[t]) {
            t++; // 锁定左右子节点中的较大者
        }
        if (heap[curr] >= heap[t]) {
            break; // 父节点已满足堆性质，提前终止下沉
        }
        swap(heap[curr], heap[t]);
        curr = t; // 更新当前节点下标，继续迭代
    }
}

int top() {
    return heap[1]; // O(1) 返回堆顶最值
}

NOIP 实战避坑指南

数组下标从 0 开始建堆导致计算坍塌部分选手习惯性地将堆顶设在 heap[0]。此时左子节点计算公式变为 $2i+1$，右子节点变为 $2i+2$，父节点变为 $\lfloor (i-1)/2 \rfloor$。在进行父节点检索时，当 $i=0$，计算 $(0-1)/2$ 在 C++ 向零取整的规则下仍为 0，这会直接引发向上的死循环。因此，手写堆必须严格从下标 1 开始存储。
Shift Down 左右儿子选择逻辑短路在进行向下堆化时，直接写出 if (heap[curr2+1] > heap[curr2]) 比较逻辑，漏掉了右儿子是否存在的边界判定 $(curr \times 2 + 1) \le sz$。若此时当前节点只有左儿子，代码会强行读取 sz+1 位置的残留脏数据参与比较。这会导致下沉路径被脏数据错误劫持，引发堆性质崩溃。

经典 NOIP/洛谷真题

1. 洛谷 P1177 【模板】排序

题意描述：给定一个长度为 $N$ 的序列，要求将其从小到大排序输出。
问题本质：全序集合的非线性输出，利用堆实现 $O(N \log N)$ 排序。
核心解题思路：构建一个小根堆。将所有元素通过 push 压入堆内，随后在循环中连续调用 top 与 pop，实现稳定排序。

核心代码（小根堆排序应用）：

// 假设此处已将前文的大根堆模板修改为了小根堆 MinHeap
MinHeap my_heap;
for (int i = 1; i <= n; ++i) {
    my_heap.push(a[i]); // 全局元素入堆
}
for (int i = 1; i <= n; ++i) {
    a[i] = my_heap.top(); // 依次取出当前全局最小值
    my_heap.pop();
}

2. 洛谷 P1090 [NOIP2004 提高组] 合并果子

题意描述：每次选取两堆重量最小的果子进行合并，体力消耗为新堆重量。求将所有果子合并为一堆的最小体力消耗。
问题本质：哈夫曼树（Huffman Tree）构造过程中的贪心策略优化。
核心解题思路：每次需要动态获取并删除全局最小的两个元素，并插入一个新元素。直接调用 STL 的优先队列来实现小根堆，将原本 $O(N^2)$ 的检索优化至 $O(N \log N)$。

核心代码（STL 优先队列写法）：

#include <queue>
#include <vector>

// 定义 STL 小根堆
priority_queue<int, vector<int>, greater<int>> pq;

int ans = 0;
// 假设 n 个果子的初始重量均已 push 入 pq
for (int i = 1; i < n; ++i) { // 合并 n 堆果子需要进行 n-1 次操作
    int a = pq.top(); pq.pop(); // 取出第一小的堆
    int b = pq.top(); pq.pop(); // 取出第二小的堆

    ans += (a + b);       // 累加本次合并体力消耗
    pq.push(a + b);       // 合并后的新堆重新入队
}
// 循环结束后 ans 即为最小总体力消耗