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

核心逻辑与数学原理

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

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

左子节点下标：$\text{left}(i) = 2i = i \times 2$
右子节点下标：$\text{right}(i) = 2i + 1 = (i \times 2) + 1$
父节点下标：$\text{parent}(i) = \frac{i}{2}$

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

$$\forall i > 1, \quad \text{heap}[\text{parent}(i)] \ge \text{heap}[i]$$

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

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

状态设计与算法推导

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

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

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

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

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

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

判定条件：寻找其左子节点 $t = curr \times 2$。若 $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++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

// 严格限定空间大小，杜绝动态内存分配带来的常数劣化
const int MAXN = 100005;

struct MaxHeap {
    int heap[MAXN];
    int sz;

    // 显式初始化，严禁依赖默认隐式构造
    MaxHeap() : sz(0) {}

    // 向上堆化：新元素入堆维护
    void push(int val) {
        heap[++sz] = val;
        int curr = sz;
        // 致命踩坑点：必须先判断 curr > 1 后访问父节点，否则当 curr=1 时 1/2 为 0 会触发越界错误
        while (curr > 1 && heap[curr] > heap[curr / 2]) {
            std::swap(heap[curr], heap[curr / 2]);
            curr /= 2;
        }
    }

    // 返回堆顶元
    int top() const {
        return heap[1];
    }

    // 向下堆化：弹出堆顶维护
    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; // 堆性质已恢复，强行切断下沉分支
            }
            std::swap(heap[curr], heap[t]);
            curr = t; // 推进迭代状态
        }
    }

    bool empty() const {
        return sz == 0;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (std::cin >> n) {
        MaxHeap my_heap;
        for (int i = 0; i < n; ++i) {
            int val;
            std::cin >> val;
            my_heap.push(val);
        }

        while (!my_heap.empty()) {
            std::cout << my_heap.top() << " ";
            my_heap.pop();
        }
        std::cout << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

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

经典 NOIP/洛谷真题

1. 洛谷 P1177 【模板】快速排序 / 排序

题意描述：给定一个长度为 $N$ 的随机序列，要求将其从小到大排序输出。
问题本质：全序集合的非线性输出，利用堆实现 $O(N \log N)$ 排序。
核心解题思路：构建一个小根堆（或大根堆）。将所有元素通过 push 操作压入手写堆内，随后在 while 循环中不断读取 top 并执行 pop。手写二叉堆在此类高强度数据排序测试中，具有比 std::sort 更加平稳的最坏复杂度保障。

2. 洛谷 P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题意描述：在一个序列中，每次选取两堆重量最小的果子进行合并，合并后的新果子堆重量为两堆之和，产生的体力消耗为新堆重量。求将所有果子合并为一堆的最小体力消耗。
问题本质：哈夫曼树（Huffman Tree）构造过程中的贪心策略优化。
核心解题思路：利用手写小根堆维护当前的果子集合。每次通过 top 与 pop 连续取出两个当前全局最小的元素 $A$ 和 $B$，将其累加进答案中，随后将合并后的新元素 $A+B$ 通过 push 重新砸回小根堆。重复此过程 $N-1$ 次，利用堆的动态维护能力将原本 $O(N^2)$ 的暴力检索优化至 $O(N \log N)$。