C++ 怎么实现堆排序 C++ make_heap与sort_heap使用【STL】_网络技术

make_heap仅构建堆结构而不排序，需配合sort_heap才能完成排序；它时间复杂度O(n)，但要求输入为随机访问迭代器，且必须与sort_heap使用相同比较函数。

make_heap 为什么不能直接当排序用

make_heap 只把容器转成最大堆（或最小堆），不保证元素有序。它只调整结构满足堆性质：每个节点值 ≥（或 ≤）其子节点，但根最大、叶子最小，并不等于“从大到小排列”。常见误用是调完 make_heap 就以为排好了，结果一打印发现顺序乱的。

典型场景：你有一段 vector v = {3,1,4,1,5};，执行 make_heap(v.begin(), v.end()); 后，v 可能变成 {5,3,4,1,1} —— 满足堆序，但不是升序/降序。

默认构造最大堆（less），想最小堆得显式传 greater()
时间复杂度 O(n)，但只是建堆，不是排序
底层依赖随机访问迭代器，list 不能用

sort_heap 必须在 make_heap 之后调用

sort_heap 的前提条件很硬：它要求输入区间**已经是合法堆**。如果直接对普通数组调 sort_heap，行为未定义，大概率崩溃或输出垃圾数据。错误现象包括：程序闪退、部分元素重复、最后几个数完全错位。

正确链条只有这一种：make_heap → （可选 push_heap/pop_heap）→ sort_heap。其中 sort_heap 是个“一次性操作”：它把堆逐个弹出最大元放到末尾，最终得到升序序列（对最大堆而言）。

对最大堆调 sort_heap 得升序；若要降序，先用 greater() 建最小堆，再调 sort_heap
调用后原堆结构被破坏，不能再当堆用
必须和 make_heap 用同一比较函数，否则结果不可预测

完整堆排序三步写法（含自定义比较）

标准堆排序流程就是三行 STL 调用，但每行参数必须对齐。例如按绝对值升序排：

vector v = {-3, 2, -1, 4};
auto abs_less = [](int a, int b) { return abs(a) < abs(b); };
make_heap(v.begin(), v.end(), abs_less);
sort_heap(v.begin(), v.end(), abs_less);
// v 现在是 {-1, 2, -3, 4}（abs: 1,2,3,4）

注意点：

lambda 捕获为空时才能作为模板参数，所以不能带 [&] 或 [=]
如果用函数对象（如 struct AbsLess { bool operator()(...) {...} };），要确保 operator() 是 const
sort_heap 不接受 std::execution::par 等策略，纯串行

性能与边界提醒：别在 vector 外反复调 heap 函数

STL 堆函数都假设容器内存连续且迭代器有效。vector 中间 erase 或 insert 后，原有堆结构全失效，必须重调 make_heap，不能靠 push_heap 补救——因为 push_heap 只处理“最后一个元素插入后”的情况，前提是前面仍是堆。

另一个易忽略点：make_heap 和 sort_heap 对空区间或单元素区间安全，但传入 v.end() 和 v.end() 这种无效范围会 UB。调试时建议加 assert：

assert(first != last && "heap op on empty range");

实际项目里，如果排序是唯一目标，直接用 std::sort 更快更稳；STL 堆函数真正价值在于需要动态维护堆结构的场景，比如优先队列底层、Top-K 流式计算——这时候才轮到 push_heap/pop_heap 上场。

# c++ # 排列 # 为什么 # less # sort # const # bool # Lambda # 堆 # Struct # operator # 对象 # 升序 # 大堆 # 迭代 # 这一 # 是个 # 好了 # 降序 # 你有 # 而不 # 仍是

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】