c++中堆排序算法如何实现_c++ heap sort代码【源码】_网络技术

堆排序核心是heapify而非完整堆类实现，应优先使用std::make_heap和std::pop_heap原地排序，建堆O(n)，需从下标(n/2)-1开始sift_down，且不稳定、缓存不友好。

堆排序的核心是 `heapify` 而不是手写完整二叉堆类

多数人误以为堆排序必须先实现一个完整的 Heap 类（带 insert、extract_max 等），其实 C++ 标准库已提供底层支持，且原地排序只需关注 heapify 过程。关键在于：堆排序本质是「建堆 + 反复弹出最大值」，而建堆可以自底向上用 std::make_heap，或手动实现 sift_down 逻辑。

常见错误现象：std::make_heap 后直接遍历数组，发现顺序不对——因为它是最大堆，顶部是最大值，但整个数组不有序；必须配合 std::pop_heap 把最大值逐步移到末尾。

std::make_heap 时间复杂度 O(n)，不是 O(n log n)；这是很多人忽略的优化点
若用 std::priority_queue 实现，会额外分配内存，失去「原地」优势
手动实现 heapify 时，最后一个非叶子节点下标是 (n / 2) - 1，不是 n / 2

用 `std::make_heap` 和 `std::pop_heap` 组合实现最简版本

这是最贴近算法导论描述、又避免重复造轮子的做法。它不引入额外容器，只操作原始数组，且可复用标准库的健壮性。

void heap_sort(std::vector& arr) {
    std::make_heap(arr.begin(), arr.end());  // 建最大堆
    for (auto it = arr.end(); it != arr.begin(); --it) {
        std::pop_heap(arr.begin(), it);  // 把堆顶移到 [it-1]
    }
}

注意：std::pop_heap 不删除元素，只是把最大值换到当前范围末尾，然后调整剩余部分为堆。所以循环中 it 从 end() 开始递减，每次缩小堆的范围。

如果传入 std::vector，需确保有随机访问迭代器（满足）
排序后是升序；若要降序，改用 std::less 作为第三个参数（默认是 std::less，即最大堆 → 升序）
对 int* 数组也适用：std::make_heap(ptr, ptr + n)

手动实现 `sift_down` 时索引边界容易错

当不用标准库、必须手写时，核心是 sift_down 函数：从某节点出发，将其下沉到合适位置。最容易出错的是左右孩子索引计算和越界判断。

假设当前节点下标为 i，则：

左孩子： 2 * i + 1（不是 2 * i，因数组从 0 开始）
右孩子： 2 * i + 2
检查是否越界：必须同时满足 left 和 right ，不能只比 arr.size()
下沉前要先比较左右孩子，选较大者再与父节点交换；否则可能破坏堆性质

建堆阶段必须从最后一个非叶子节点开始倒序调用 sift_down，否则无法保证整体堆结构。这个节点是 (arr.size() / 2) - 1，不是 arr.size() / 2

或 arr.size() - 1。

性能与稳定性：堆排序不适合小数组，也不稳定

堆排序时间复杂度稳定在 O(n log n)，但常数因子比快排大；实际中，STL 的 std::sort 通常用 introsort（快排+堆排兜底），而非纯堆排。

对少于 ~32 个元素的数组，插入排序更快；标准库实现通常会切分处理
堆排序不稳定：相等元素的相对位置可能改变，比如用于结构体排序时要注意字段相等性
缓存不友好：sift_down 的跳转访问模式导致 CPU cache miss 高于归并或快排

如果你真需要手写堆排序，优先考虑复用 std::make_heap + std::pop_heap；手动实现只在教学、嵌入式无 STL 或定制比较逻辑时才值得投入。

# c++ # 排序算法 # 标准库 # less # sort # 结构体 # 插入排序 # int # 循环 # 堆 # 算法 # 这是 # 升序 # 大堆 # 而非 # 不稳定 # 移到 # 复用 # 的是 # 不友好 # 也不

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