C++ 怎么实现堆排序 C++ make_heap与sort_heap教程【堆】

make_heap 和 sort_heap 是 c++ 标准库中用于原地构建和排序最大堆的函数，必须按 make_heap→sort_heap 顺序调用；单独使用 sort_heap 会导致未定义行为。

make_heap 和 sort_heap 是什么，能不能直接拿来排序

make_heap 和 sort_heap 是 C++ 标准库 中提供的堆操作函数，不是“排序函数”，而是**原地维护最大堆结构的工具**。它们本身不直接等价于堆排序全过程，但组合使用就是标准堆排序的底层实现方式。

常见误解是调用一次 sort_heap 就能排好序 —— 实际上它**只对已满足堆性质的序列有效**。如果数组没建堆，直接 sort_heap 会得到错误结果（比如乱序、重复元素、甚至未定义行为）。

正确流程必须是：make_heap → sort_heap，中间不能插入其他修改操作。

怎么用 make_heap 建堆，要注意哪些坑

make_heap 默认构建的是**最大堆**（根节点最大），时间复杂度 O(n)，比逐个 push_heap 更高效。

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

• 必须传入随机访问迭代器，比如 vector 或原生数组指针
• 默认按 operator 比较，若要最小堆，得显式传 greater()
• 建堆后，容器逻辑顺序 ≠ 排序顺序 —— 此时只是满足堆性质，首元素最大，其余无序
• 建堆不改变容器大小，也不分配新内存，纯原地重排

示例：

vector v = {3, 1, 4, 1, 5}; make_heap(v.begin(), v.end()); // → v 变成 {5, 3, 4, 1, 1}（一种合法最大堆结构）

sort_heap 为什么必须在 make_heap 之后调用

sort_heap 的作用是：**把一个合法的最大堆，原地排序为升序序列**（从小到大）。它反复执行“取走根（最大值），放末尾；剩余部分重新下滤”，本质就是堆排序的第二阶段。

如果输入不是堆，sort_heap 的下滤逻辑会崩溃或产生任意结果 —— 它不校验输入，也不尝试修复。

关键点：

• sort_heap 不改变容器 size，但会重排全部元素
• 它要求区间是“有效最大堆”，否则行为未定义
• 调用后，原堆结构被破坏，得到升序排列（注意：不是降序）
• 不能对 const 容器或只读区间调用

接上例：

make_heap(v.begin(), v.end()); sort_heap(v.begin(), v.end()); // → v 变成 {1, 1, 3, 4, 5}

自己写堆排序时，还该不该用 make_heap/sort_heap

如果你在面试或算法课里被要求“手写堆排序”，那应该手动实现 sift_down 和建堆逻辑 —— 否则等于没考你对堆的理解。

但在工程代码中，优先用 make_heap + sort_heap，因为：

• 经过充分测试，边界安全（比如空容器、单元素、重复值）
• 编译器可能做优化（如 libc++ 的 block-wise 下滤）
• 避免手误写错父子索引（2*i+1 vs 2*i+2）或越界检查

不过要注意：这两个函数操作的是**左闭右开区间**，和 sort 一致；且不支持自定义分配器或移动语义的显式控制 —— 如果你需要这些，就得自己封装。

真正容易被忽略的是：建堆和排序之间不能有插入/删除/修改操作，也不能跨线程并发访问同一容器 —— 它们不是线程安全的。