C++如何实现堆排序_C++ make_heap与sort_heap算法步骤

堆排序利用C++标准库的make_heap和sort_heap函数实现，先调用make_heap构建最大堆，再用sort_heap排序为升序；通过greater可创建最小堆并得降序结果，操作简便高效。

堆排序是一种基于二叉堆数据结构的比较排序算法，C++标准库提供了make_heap和sort_heap两个函数来简化这一过程。它们定义在头文件中，可以直接对容器或数组进行操作。

1. 堆的基本概念与C++中的接口

堆是一种完全二叉树，分为最大堆和最小堆。在最大堆中，父节点的值总是大于等于子节点。C++默认使用最大堆。

make_heap将一段区间转化为堆结构，sort_heap则对已构建的堆进行排序。

常用操作：

• make_heap(first, last)：构造最大堆
• sort_heap(first, last)：将堆排序为有序序列
• push_heap(first, last)：插入新元素后维护堆
• pop_heap(first, last)：移除堆顶后维护堆

2. 使用 make_heap 构建堆

调用make_heap可以将一个容器（如vector）重新排列成堆结构。

示例代码：

vector nums = {3, 1, 4, 1, 5, 9, 2, 6};
make_heap(nums.begin(), nums.end()); // 构建最大堆
// 此时nums[0]是最大值

此时容器满足堆性质，但元素不是有序的。

3. 使用 sort_heap 进行排序

必须先调用make_heap，然后才能使用sort_heap进行排序。

完整排序示例：

vector nums = {3, 1, 4, 1, 5, 9, 2, 6};
make_heap(nums.begin(), nums.end());
sort_heap(nums.begin(), nums.end()); // 排序后变为升序

注意：sort_heap会将最大堆按升序排列，因为每次把最大值移到末尾。

4. 自定义比较函数

如果需要最小堆或自定义排序规则，可以传入比较函数。

例如创建最小堆：

vector nums = {3, 1, 4, 1, 5, 9, 2, 6};
make_heap(nums.begin(), nums.end(), greater());
sort_heap(nums.begin(), nums.end(), greater()); // 升序变降序？

注意：使用greater时，sort_heap结果是降序。因为堆顶是最小值，不断移到末尾形成反向排列。

基本上就这些。C++的堆算法封装得很好，适合快速实现堆排序而无需手动调整堆结构。