建模。底层用 std::vector<int> 按层序存完全二叉树（下标映射见知识点）。不变量：任何时刻数组都满足小顶堆序（父 \(\le\) 子）。push 破坏后用 sift-up 修复，pop 用末元素补位后用 sift-down 修复。

代码。

#include <cstddef>
#include <vector>
#include <utility>
#include <stdexcept>

class MinHeap {
public:
    void push(int v) {
        heap_.push_back(v);                 // 放到末尾，保持完全性
        siftUp((int)heap_.size() - 1);      // 与父交换直至堆序恢复
    }

    int top() const {
        if (heap_.empty()) throw std::out_of_range("empty heap");
        return heap_[0];                    // 堆顶即全局最小
    }

    void pop() {
        if (heap_.empty()) throw std::out_of_range("empty heap");
        heap_[0] = heap_.back();            // 末元素补位
        heap_.pop_back();
        if (!heap_.empty()) siftDown(0);    // 下沉恢复堆序
    }

    bool empty() const { return heap_.empty(); }
    std::size_t size() const { return heap_.size(); }

private:
    static int parent(int i) { return (i - 1) / 2; }

    void siftUp(int i) {
        while (i > 0 && heap_[parent(i)] > heap_[i]) {
            std::swap(heap_[i], heap_[parent(i)]); // 与父交换
            i = parent(i);
        }
    }

    void siftDown(int i) {
        int n = (int)heap_.size();
        while (true) {
            int best = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && heap_[l] < heap_[best]) best = l;  // 取较小孩子
            if (r < n && heap_[r] < heap_[best]) best = r;
            if (best == i) break;                     // 已比两个孩子都小
            std::swap(heap_[i], heap_[best]);
            i = best;
        }
    }

    std::vector<int> heap_;
};

数值演示。依次 push 5、3、8、1：插入 1 后位于下标 3，其父（下标 1，值 3）大于 1，交换；再与堆顶 5 交换，数组变为 [1,3,8,5]。pop()：末元素 5 补位为 [5,3,8]，5 与较小孩子 3 交换得 [3,5,8]，堆顶返回值 1。

复杂度。push 与 pop 均 \(O(\log n)\)（路径长度 \(\le \lfloor \log_2 n \rfloor\)），top 与 empty 为 \(\Theta(1)\)。空堆 pop 直接抛异常，fail-fast。

边界。空堆/单元素堆（siftDown 中孩子下标越界检查 \(l \lt n\)、\(r \lt n\) 必须有）；相等元素（交换条件用严格大于，允许相等共存）；大顶堆只需把两个比较符号反过来。变式追问「合并两个堆」：二叉堆不支持高效合并，需要斜堆/二项堆等可合并堆，能点名即可。

面试怎么讲。先写下标映射三公式，再讲「插入上浮、删除下沉」的对称性，数值演示一遍 push-pop 全过程；被问「堆为什么不是有序数组」时，答「层序数组无序、只有堆顶最值保证，排序要靠反复取顶」。

建模。两阶段：先在原数组上自底向上建大顶堆（倒数第一个非叶开始 sift-down）；再每轮「堆顶与堆区末尾交换、堆区减一、新顶下沉」。不变量：数组尾部 \(a[\text{end}..n-1]\) 是已排好的最大值降序前缀，\(a[0..\text{end}-1]\) 仍是合法大顶堆。

代码。

#include <vector>
#include <utility>

void siftDownMax(std::vector<int>& a, int i, int n) { // 大顶堆下沉
    while (true) {
        int best = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[best]) best = l;      // 取较大孩子
        if (r < n && a[r] > a[best]) best = r;
        if (best == i) break;
        std::swap(a[i], a[best]);
        i = best;
    }
}

void heapSort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; --i)   // 阶段一：建大顶堆，O(n)
        siftDownMax(a, i, n);
    for (int end = n - 1; end > 0; --end) { // 阶段二：反复取堆顶，O(n log n)
        std::swap(a[0], a[end]);            // 当前最大值归位
        siftDownMax(a, 0, end);             // 堆区缩小为 end
    }
}

数值演示。a = [4,10,3,5,1]：建堆阶段对下标 1、0 依次下沉，得到大顶堆 [10,5,3,4,1]；第一轮交换 a[0]、a[4] 得 [1,5,3,4,10]，堆区 [1,5,3,4] 下沉修复为 [5,4,3,1]；如此再三轮，最终 [1,3,4,5,10]。

复杂度。建堆 \(O(n)\)（级数证明见知识点），\(n-1\) 轮取顶各 \(O(\log n)\)，总 \(O(n \log n)\) 且最坏也是 \(O(n \log n)\)（与快排的平均/最坏分裂对照）。额外空间 \(O(1)\)：只有交换的临时量与下标。不稳定：相等元素会被远距离交换分开。

边界。空数组与单元素（两个循环都不执行，直接返回）；全相等元素（比较全不触发交换，仍线性对数但无实际移动）；n 为 1 时建堆起点 \(n/2 - 1 = -1\)，循环条件自然跳过。追问「降序怎么办」：建小顶堆即可，机制对称。

面试怎么讲。把「建堆 O(n)」与「取顶 n log n」分开报复杂度，并给出级数求和的一句话证明；主动对比：堆排最坏稳、快排平均快、归并稳但要 \(O(n)\) 空间——三者取舍的完整论述在007 章。

建模。两步：哈希表统计频次 \(O(n)\)；再在「(频次, 元素) 对」上求频次前 k 大。用大小为 k 的小顶堆维护冠军组，堆顶是组内频次最低者（门槛）；扫描每个不同元素，赢过门槛就替换。

代码。

#include <vector>
#include <queue>
#include <utility>
#include <unordered_map>

std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
    std::unordered_map<int,int> freq;
    for (int x : nums) ++freq[x];               // 第一步：计数 O(n)

    using P = std::pair<int,int>;               // (频次, 元素)
    auto byFreq = [](const P& a, const P& b) { return a.first > b.first; };
    std::priority_queue<P, std::vector<P>, decltype(byFreq)> pq(byFreq);
                                               // 比较器 greater 语义 = 小顶堆
    for (const auto& kv : freq) {
        pq.push(kv);
        if ((int)pq.size() > k) pq.pop();       // 踢掉门槛
    }

    std::vector<int> ans;
    while (!pq.empty()) { ans.push_back(pq.top().second); pq.pop(); }
    return ans;
}

数值演示。nums = [1,1,1,2,2,3]，k = 2：频次表 {1:3, 2:2, 3:1}。堆容量 2：入 (3,1)、(2,2)；入 (1,3) 时堆超容，踢掉 (1,3) 自己——即 3 被门槛淘汰。最终输出 [2,1]（或 [1,2]，题目通常不要求堆内顺序）。

复杂度。计数 \(O(n)\)；不同元素数 \(m \le n\)，堆操作至多 \(m\) 次每次 \(O(\log k)\)，总 \(O(n + m \log k)\subseteq O(n \log k)\)。空间：哈希 \(O(m)\) + 堆 \(O(k)\)。

边界。k 等于不同元素个数（全保留，不踢任何人）；k = 1（退化成求众数，可以直接一次扫描）；频次并列时题目一般允许任意 k 个（要向面试官确认口径）。若数组是流式到达的，本解法无需任何修改即可在线维护——这是它对「全排序」的决定性优势。

面试怎么讲。先报三方案复杂度表（全排序 / 堆 / QuickSelect），说明为什么选堆（流式、空间 \(O(k)\)）；「求前 k 大配小顶堆」这句方向口诀必须说出口，方向反了这题就写反了。

建模。节点 = 26 个孩子指针 + 词尾标记。insert 沿路径建节点并在终点标 isEnd；search 要求路径存在且终点有标记；startsWith 只要求路径存在。不变量：任意时刻树中每条「根到节点」的路径都对应集合中某词的某个前缀。

代码。

#include <array>
#include <string>

class Trie {
public:
    Trie() : root_(new Node()) {}
    ~Trie() { destroy(root_); }

    void insert(const std::string& word) {
        Node* cur = root_;
        for (char ch : word) {
            int c = ch - 'a';
            if (cur->children[c] == nullptr)
                cur->children[c] = new Node();   // 按需建节点
            cur = cur->children[c];
        }
        cur->isEnd = true;                       // 词尾标记
    }

    bool search(const std::string& word) const {
        const Node* node = walk(word);
        return node != nullptr && node->isEnd;    // 路径通且到词尾
    }

    bool startsWith(const std::string& prefix) const {
        return walk(prefix) != nullptr;           // 只要路径存在
    }

private:
    struct Node {
        std::array<Node*, 26> children{};        // 值初始化为 nullptr
        bool isEnd = false;
    };

    const Node* walk(const std::string& s) const { // 公共路径行走
        const Node* cur = root_;
        for (char ch : s) {
            cur = cur->children[ch - 'a'];
            if (cur == nullptr) return nullptr;   // 路径断开
        }
        return cur;
    }
    static void destroy(Node* n) {
        if (n == nullptr) return;
        for (Node* c : n->children) destroy(c);
        delete n;
    }

    Node* root_;
};

数值演示。依次 insert("quant")、insert("quantile")：前 5 个字符的路径完全共享，"quant" 终点标 isEnd 后，"quantile" 继续向下延伸 3 个节点。此时 search("quant") = true，search("quan") = false，startsWith("quan") = true，startsWith("quantx") = false。

复杂度。三操作均为 \(O(L)\)，与词表大小无关；空间最坏 \(O(26 N)\)（\(N\) 为全部字符数，前缀几乎不共享时），前缀共享越多越省。析构递归深度为词长，正常使用无栈风险。

边界。空串（insert("") 只标根的 isEnd，此时 root 既是前缀状态又是词尾）；非小写字符（需先约定字符集或换 map<char,Node*> 孩子）；内存口径（26 叉数组版 vs map 版的空间/时间取舍，面试要能主动对比）。追问应用：自动补全、拼写检查、按前缀计数、以及「用 Trie 求最大异或对」的思想延伸（路径即决策）。

面试怎么讲。先画 {quant, quantile} 的共享路径图说明「前缀复用」，再指出 search 与 startsWith 的唯一区别是 isEnd 检查，最后给出「\(O(L)\) 与集合大小无关」的卖点与空间代价——答案就完整了。