c++中如何实现堆排序_c++ heap算法与堆排序代码【实例】

不建议手写堆排序，应使用STL的std::make_heap、std::push_heap、std::pop_heap和std::sort_heap；它们已优化正确性、性能与边界处理，支持自定义比较器且要求随机访问迭代器。

堆排序在 C++ 中不建议手写完整逻辑，std::make_heap、std::pop_heap、std::push_heap 和 std::sort_heap 这组算法已封装好底层堆操作，正确性、性能和边界处理都经过严格验证。

为什么不用自己实现 heapify？

手写堆调整容易出错，尤其在索引计算（0-based vs 1-based）、父子节点关系（2*i+1 和 2*i+2）、下沉/上浮终止条件上。STL 的堆算法基于随机访问迭代器设计，对 vector、array 等容器开箱即用，且支持自定义比较器。

• 下标越界、父子交换遗漏、循环终止过早是手写最常踩的坑

• 

  std::make_heap 是原地建堆，时间复杂度 O(n)，不是 O(n log n)
• 所有 STL 堆算法都要求容器支持随机访问，list 或 deque 不可用

std::make_heap + std::sort_heap 实现升序排序

这是最直接的堆排序调用方式：先建最大堆，再逐个弹出最大值到末尾。注意——std::sort_heap 要求输入已是有效堆，否则行为未定义。

std::vector v = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(v.begin(), v.end());        // 建最大堆
std::sort_heap(v.begin(), v.end());         // 原地升序排列
// v 变为 {1, 1, 2, 3, 4, 5, 6, 9}

• 默认构造最大堆，所以 sort_heap 得到升序结果
• 若要降序，需传入 std::greater()：std::make_heap(v.begin(), v.end(), std::greater())
• std::sort_heap 只能调用一次；调用后容器不再满足堆性质，再次调用会崩溃或产生乱序

边插入边维护堆：用 push_heap 和 pop_heap

适合动态场景，比如实时 Top-K 统计、优先队列模拟。必须保证插入前容器已是合法堆，且新元素已置于末尾（push_back）。

std::vector heap = {10, 5, 8};
std::make_heap(heap.begin(), heap.end());  // 先建堆

heap.push_back(12);                        // 新元素放末尾
std::push_heap(heap.begin(), heap.end());  // 上浮调整

// 弹出最大值（仍在末尾，需手动 pop）
std::pop_heap(heap.begin(), heap.end());   // 最大值移到末尾
int top = heap.back();
heap.pop_back();                           // 真正移除

• push_heap 不负责插入，只做上浮；你得先 push_back
• pop_heap 不删除元素，只把堆顶换到末尾；必须配 pop_back 才算真正弹出
• 所有操作都是 O(log n)，但频繁调用时要注意 vector 的扩容成本

自定义比较器与稳定性注意事项

堆排序本身不稳定（相等元素的相对顺序可能改变），STL 实现也不例外。若需稳定，不能依赖堆算法，得换方案（如 std::stable_sort 配合自定义 key）。

• 自定义类型必须提供可比性，或显式传入比较器：[](const auto& a, const auto& b) { return a.priority
• 比较器语义必须一致：建堆、push/pop、sort_heap 都要用同一个
• 别用 std::less 以外的函数对象捕获局部变量，除非确保生命周期覆盖整个堆操作过程

真正需要“手写堆排序”的场景极少——要么是教学理解堆结构，要么是嵌入式环境无 STL。工程中优先用标准算法，省去索引错位、边界越界、比较器漏传这些隐蔽问题。