堆排序的核心思路是先构建一个大顶堆或者小顶堆，然后不断将堆顶元素和末尾元素交换，再调整剩余元素为堆，最终得到有序序列。C++的STL标准库已经封装了堆操作的相关函数，其中make_heap用于构建堆，sort_heap用于将堆转换为有序序列，开发者不需要手动实现堆的调整逻辑就能快速完成堆排序。
STL堆操作函数基础说明
STL的堆相关函数定义在<algorithm>头文件中，常用的两个核心函数作用如下：
- make_heap：将一段迭代器范围内的元素构建成大顶堆，默认使用小于比较器，堆顶元素为最大值。
- sort_heap：将已经是大顶堆的序列转换为升序序列，调用后原堆结构会被破坏。
这两个函数的迭代器范围遵循左闭右开原则，和STL其他算法的迭代器规则一致。
使用make_heap和sort_heap实现堆排序
使用STL函数实现堆排序的步骤非常简单，只需要三步：首先准备待排序的容器，然后调用make_heap构建大顶堆，最后调用sort_heap得到有序序列。
基础示例代码
下面是一个使用vector容器配合STL函数实现堆排序的完整示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 待排序的数组
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
// 第一步：构建大顶堆
make_heap(arr.begin(), arr.end());
cout << "构建大顶堆后：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
// 第二步：将堆转换为升序序列
sort_heap(arr.begin(), arr.end());
cout << "堆排序完成后：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
上述代码的输出结果如下：
构建大顶堆后：9 6 4 1 5 1 2 3 堆排序完成后：1 1 2 3 4 5 6 9
自定义比较器使用
如果需要构建小顶堆或者自定义排序规则，可以给make_heap和sort_heap传入自定义的比较函数，两者使用的比较器需要保持一致，否则会导致结果错误。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
// 构建小顶堆，使用greater比较器
make_heap(arr.begin(), arr.end(), greater<int>());
cout << "构建小顶堆后：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
// 转换为降序序列
sort_heap(arr.begin(), arr.end(), greater<int>());
cout << "降序排序完成后：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
手动实现堆排序与STL实现的对比
如果不使用STL的make_heap和sort_heap函数，我们也可以手动实现堆排序的逻辑，核心需要实现堆的调整函数，下面是手动实现的示例代码：
#include <iostream>
#include <vector>
using namespace std;
// 调整堆的函数，将以i为根的子树调整为大顶堆
void heapAdjust(vector<int>& arr, int i, int len) {
int temp = arr[i];
// 从i的左子节点开始调整
for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
// 如果右子节点更大，就指向右子节点
if (k + 1 < len && arr[k] < arr[k + 1]) {
k++;
}
// 如果子节点比父节点大，就交换
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
// 手动实现堆排序
void heapSort(vector<int>& arr) {
int len = arr.size();
// 从最后一个非叶子节点开始构建大顶堆
for (int i = len / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, len);
}
// 依次将堆顶元素和末尾元素交换，再调整堆
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapAdjust(arr, 0, i);
}
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
heapSort(arr);
cout << "手动实现堆排序结果：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
手动实现堆排序需要开发者理解堆的调整逻辑，代码量更多，但是可以更深入理解堆排序的底层原理。而使用STL的make_heap和sort_heap函数则更加简洁，不需要关注底层调整细节，适合快速开发场景。
使用注意事项
- 调用sort_heap之前，必须保证序列已经是堆结构，否则排序结果会错误。
- make_heap和sort_heap使用的比较器必须一致，否则会导致未定义行为。
- 堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，是不稳定排序算法。
- 如果只需要获取堆顶元素而不需要完整排序，不需要调用sort_heap，直接取容器第一个元素即可。