堆排序的核心逻辑是借助大顶堆或小顶堆的特性完成排序，大顶堆的父节点值始终大于等于子节点值，小顶堆则相反。排序时先构建初始堆，再不断交换堆顶元素和末尾元素，重新调整堆结构，直到所有元素有序。
堆排序的核心原理
堆排序分为两个关键步骤，首先是建堆，其次是排序调整。建堆的过程是从最后一个非叶子节点开始，向上依次调整每个节点，保证每个节点都满足堆的性质。排序阶段每次将堆顶元素（最大或最小值）和当前堆的最后一个元素交换，然后将堆的大小减一，再对新的堆顶进行调整，重复这个过程直到堆中只剩一个元素。
手动实现堆排序
下面以升序排序为例，使用大顶堆实现堆排序，完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
// 调整堆的函数，确保以root为根的子树满足大顶堆性质
void heapAdjust(vector<int>& arr, int root, int heapSize) {
int left = 2 * root + 1; // 左子节点索引
int right = 2 * root + 2; // 右子节点索引
int largest = root; // 假设当前根节点是最大值
// 如果左子节点存在且值大于当前最大值，更新最大值索引
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点存在且值大于当前最大值，更新最大值索引
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是当前根节点，交换位置并递归调整受影响的子树
if (largest != root) {
swap(arr[root], arr[largest]);
heapAdjust(arr, largest, heapSize);
}
}
// 堆排序主函数
void heapSort(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return;
// 构建大顶堆，从最后一个非叶子节点开始调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, n);
}
// 逐步将堆顶元素移到末尾，调整堆
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]); // 交换堆顶和当前末尾元素
heapAdjust(arr, 0, i); // 调整剩余元素为堆
}
}
int main() {
vector<int> testArr = {4, 10, 3, 5, 1, 8, 7, 2, 6, 9};
cout << "排序前数组：";
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
heapSort(testArr);
cout << "排序后数组：";
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
return 0;
}
上述代码中，heapAdjust函数用于调整单个节点的堆结构，heapSort函数先完成建堆，再通过循环交换和调整完成排序。运行后输出的排序前数组为4 10 3 5 1 8 7 2 6 9，排序后数组为1 2 3 4 5 6 7 8 9 10。
C++标准库heap算法应用
C++标准库的<algorithm>头文件中提供了现成的堆操作函数，不需要手动实现调整逻辑，常用的函数如下：
make_heap：将一段区间的元素构建成堆，默认是大顶堆push_heap：向堆中添加一个元素，需要先添加元素到容器末尾再调用该函数pop_heap：将堆顶元素移到容器末尾，然后调整剩余元素为堆sort_heap
下面是使用标准库heap算法实现升序排序的示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> testArr = {4, 10, 3, 5, 1, 8, 7, 2, 6, 9};
cout << "排序前数组：";
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
// 构建大顶堆
make_heap(testArr.begin(), testArr.end());
// 对堆进行排序，排序后堆结构失效
sort_heap(testArr.begin(), testArr.end());
cout << "排序后数组：";
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
return 0;
}
如果需要小顶堆，可以在调用make_heap时传入第三个参数greater<int>()，示例如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
vector<int> testArr = {4, 10, 3, 5, 1, 8, 7, 2, 6, 9};
// 构建小顶堆
make_heap(testArr.begin(), testArr.end(), greater<int>());
// 小顶堆排序后是降序
sort_heap(testArr.begin(), testArr.end(), greater<int>());
cout << "小顶堆排序后数组：";
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
return 0;
}
堆排序的实战场景
堆排序适合处理大规模数据的排序，尤其是在需要获取前N个最大或最小元素的场景，比如TopK问题。使用堆处理TopK问题时，不需要对所有数据排序，只需要维护一个大小为K的堆，时间复杂度可以降到O(nlogK)，比全量排序效率更高。另外，堆排序是不稳定排序，原地排序，不需要额外的存储空间，在内存受限的场景中也有不错的表现。