手写 std::priority_queue

使用动态数组和二叉堆实现优先队列，推导 sift_up、sift_down 与建堆复杂度。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

一、学习目标

掌握数组下标与堆结构映射
实现 push/pop/top
证明自底向上建堆为 O(n)

二、前置条件

完成 vector 和 stack 篇，熟悉完全二叉树。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

三、问题与设计选择

默认最大堆。节点 i 的父节点为 (i-1)/2，子节点为 2i+1 与 2i+2；比较器定义低优先级关系。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

四、内存布局与核心不变量

对所有非根节点 i，父节点的优先级不低于 i；根节点始终是当前最高优先级元素。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

五、核心实现

void sift_up(std::size_t child) {
    while (child > 0) {
        const auto parent = (child - 1) / 2;
        if (!compare_(data_[parent], data_[child])) break;
        std::swap(data_[parent], data_[child]);
        child = parent;
    }
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<class T, class Container = vector<T>, class Compare = std::less<T>>
class priority_queue {
    Container data_;
    Compare compare_{};
    void sift_up(std::size_t child) {
        while (child) {
            const std::size_t parent = (child - 1) / 2;
            if (!compare_(data_[parent], data_[child])) break;
            std::swap(data_[parent], data_[child]);
            child = parent;
        }
    }
    void sift_down(std::size_t parent) {
        while (true) {
            std::size_t best = parent;
            const std::size_t left = parent * 2 + 1;
            const std::size_t right = left + 1;
            if (left < data_.size() && compare_(data_[best], data_[left])) best = left;
            if (right < data_.size() && compare_(data_[best], data_[right])) best = right;
            if (best == parent) return;
            std::swap(data_[parent], data_[best]);
            parent = best;
        }
    }
public:
    bool empty() const noexcept { return data_.empty(); }
    std::size_t size() const noexcept { return data_.size(); }
    const T& top() const { return data_.front(); }
    void push(T value) {
        data_.push_back(std::move(value));
        sift_up(data_.size() - 1);
    }
    void pop() {
        std::swap(data_.front(), data_.back());
        data_.pop_back();
        if (!data_.empty()) sift_down(0);
    }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

七、使用示例与输出

预期输出或状态：

插入 3、1、5、2 后连续 top/pop 输出 5 3 2 1。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

八、复杂度与失效规则

操作	复杂度	说明
top	O(1)	读取根
push	O(log n)	向上调整
pop	O(log n)	末尾换根并向下调整
heapify	O(n)	自底向上

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

九、异常安全与资源管理

获取资源后立即交给 RAII 对象或明确记录已构造数量。
用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
只有在所有后续步骤不会失败时才修改不可回滚的链接。
析构、释放和关闭路径不得抛异常。
并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

十、常见错误

1. 比较器方向与 sort 的直觉相反

比较器方向与 sort 的直觉相反会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. pop 时忘记先交换根与末尾

pop 时忘记先交换根与末尾会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 声称 heapify 是 O(n log n)

声称 heapify 是 O(n log n)会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

为什么建堆是 O(n)？
如何实现最小堆？
优先队列为什么不适合任意元素删除？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

十二、练习与自测

实现 sift_down
支持批量 range 构造
解决 Top K 高频元素问题

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

十三、官方资料与延伸阅读

上一篇：手写 std::queue ｜下一篇：手写红黑树内核