C++怎么实现堆排序_C++优先队列教程【高效】

堆排序在c++中应优先使用std::make_heap、std::pop_heap、std::sort_heap三步完成，而非手写堆；std::priority_queue默认为最大堆，需显式指定std::greater实现最小堆；手写堆需注意索引公式、边界检查与sift_down顺序。

堆排序的核心不是手写堆，而是用 std::make_heap 三步到位

堆排序在 C++ 里真没必要从 sift_down 开始造轮子。标准库已经提供完整支持，关键在于理解三步操作的语义和顺序：std::make_heap、std::pop_heap、std::sort_heap。它们不是独立函数，而是一套协作协议——先建堆，再逐个弹出最大值到尾部，最后原地有序。

常见错误是把 std::pop_heap 当成“删除最大值”，其实它只是把堆顶换到末尾、然后重排剩余部分，容器大小不变。必须配合 vector.pop_back() 才算真正移除；否则下一次调用会越界或逻辑错乱。

• std::make_heap(v.begin(), v.end())：默认建最大堆（升序排序用）
• 循环调用 std::pop_heap(v.begin(), v.end() - i)（i 是已弹出个数），再执行 v.pop_back()
• 如果只想要排序结果，直接 std::sort_heap(v.begin(), v.end()) ——但前提是它已经是合法堆

优先队列 std::priority_queue 默认是最大堆，别被名字骗了

std::priority_queue 名字叫“优先队列”，行为却是取最大值，这和多数人直觉相反（比如任务调度常要最小截止时间）。它底层默认用 std::less<t></t>，所以 top() 返回最大元素。想变成最小堆？得显式传比较器：

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

注意三个模板参数缺一不可：元素类型、容器类型、比较器。漏掉 std::vector<int></int> 会导致编译失败，错误信息类似 "no type named 'value_type' in 'std::less<int>'"</int>。

立即学习“C++免费学习笔记（深入）”；

• 插入用 push()，取顶用 top()，弹出用 pop()（不返回值）
• size() 和 empty() 安全，但没有 find() 或遍历接口——它不是容器，是适配器
• 性能上，push() 和 pop() 都是 O(log n)，但内存局部性不如 vector 原生堆操作

手写堆时最容易崩在索引计算和边界条件上

如果你非得实现一个最小堆类，90% 的 bug 出在两个地方：父/子节点索引公式写反，以及 sift_down 里没处理“只有一个子节点”的情况。数组下标从 0 开始时，左子节点是 2*i + 1，右子是 2*i + 2，父节点是 (i-1)/2（整除）。别用 i/2，那适用于下标从 1 开始的教材伪代码。

另一个坑是 sift_down 过程中，比较前必须先检查子节点是否越界。例如判断右子是否存在，不能只写 right ，还要确保 <code>left 已成立，否则 <code>right 可能是负数或溢出。

• 建堆用 sift_down 从最后一个非叶子节点开始（索引 (size-2)/2），不是从 0
• 插入新元素用 sift_up，从末尾往上比，比父小就交换（最小堆）
• C++ 中用 std::swap(a[i], a[parent]) 比手动赋值更安全，避免自赋值问题

std::make_heap 和 std::priority_queue 的内存与缓存差异

两者都基于完全二叉树，但内存布局不同：std::make_heap 直接操作原始 vector，数据连续，CPU 缓存友好；std::priority_queue 是对容器的封装，虽然底层也是 vector，但每次 push 可能触发多次内存拷贝（尤其存对象时）。如果元素类型大且移动代价高，建议用 emplace() 替代 push()，避免临时对象构造。

兼容性方面，std::make_heap 要求迭代器是随机访问，std::list 不行；std::priority_queue 第二个模板参数强制要求支持 push_back 和随机访问（所以 deque 可以，list 不行）。

• 大数据量排序优先用 std::make_heap + std::sort_heap，少一次内存分配
• 动态增删场景用 std::priority_queue，但注意它不支持修改已有元素优先级
• 需要改优先级？要么用 std::set 模拟，要么自己维护索引映射，别硬刚堆结构

堆结构看着简单，但索引偏移、边界检查、比较器语义、内存模型这四点串起来，就是容易静默出错的地方。动手前先想清楚：你要的是排序结果，还是持续的动态最大值查询。