目录
前言
堆排序算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解堆排序算法。
一、什么是堆排序
堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一个近似完全二叉树的结构，分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值；而在最小堆中，父节点的值总是小于或等于其子节点的值。堆排序通常使用最大堆来升序排序数组，使用最小堆则可以降序排序数组。
二、堆排序算法的主要步骤
1.构建最大堆：
从最后一个非叶子节点开始，向上至根节点，逐个节点进行堆化。
堆化过程：对于当前节点，如果其任一子节点的值大于当前节点的值，则交换它们，并继续对受影响的子树进行堆化，直到树满足最大堆的性质。
2.排序过程：
将堆顶元素（即最大值）与堆的最后一个元素交换，此时堆的大小减1（排除已排序的最大元素）。
对新的堆顶元素进行堆化，使其满足最大堆性质。
重复上述步骤，直到堆的大小为1，此时数组已完全排序。
三、算法特性
1.原地排序：堆排序不需要额外的存储空间来存储待排序的元素，它只需要一个与待排序元素数量相等的数组空间。
2.时间复杂度：堆排序的时间复杂度为O(n log n)，其中n是待排序元素的数量。这个复杂度在最好、最坏和平均情况下都是一致的，因此它的性能是稳定的。
3.不稳定性：堆排序是一种不稳定的排序算法，因为相同元素的相对位置可能会因为堆的调整而发生变化。
4.适用性：堆排序在处理大规模数据集时具有显著的优势，因为它在构建堆和调整堆的过程中是逐步进行的，不需要像快速排序那样递归地划分数据。
四、算法优缺点
1.优点：
时间复杂度稳定，为O(n log n)。
原地排序，不需要额外的存储空间。
可以很容易地处理大量数据，适用于无法一次性加载整个数据集的情况。
可以作为优先级队列的基础，实现高效的插入、删除和获取操作。
2.缺点：
堆排序是一种不稳定的排序算法。
在数据规模较小时，堆排序的性能可能并不如一些简单的排序算法（如插入排序、选择排序等）好，因为堆排序需要额外的建堆开销，并且其实现相对复杂。
堆排序在构建堆和调整堆的过程中，需要频繁地访问父节点和子节点，这种访问模式可能会导致CPU缓存的命中率降低，从而影响排序的效率。但在大多数情况下，这个缺点并不明显，因为堆排序的整体时间复杂度仍然是O(n log n)。
五、应用场景
堆排序在许多实际应用场景中发挥着重要的作用，包括：
1.构建优先队列：堆排序是构建优先队列的一种常用方法，优先队列是一种特殊的队列，它可以按照元素的优先级对其进行排序，使得优先级最高的元素能够首先被取出。
2.处理大规模数据集：堆排序在处理大规模数据集时具有显著的优势，因为它只需要维护部分数据的堆结构，而不需要将所有数据都加载到内存中进行排序。
3.查找最大（或最小）的K个元素：通过维护一个大小为K的最小堆（或最大堆），可以在O(n log K)的时间复杂度内找到最大（或最小）的K个元素。
4.图算法：堆排序在图算法中也有广泛的应用，例如最短路径算法Dijkstra和Prim的实现中就使用了最小堆来维护待选节点的集合，并选择优先级最高的节点进行处理。
综上所述，堆排序是一种高效、灵活的排序算法，在众多实际应用场景中发挥着重要的作用。
六、堆排序算法动态图解
七、c++代码模板
#include <iostream>
#include <vector>
// 堆化函数，用于维护堆的性质
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i; // 初始化largest为根节点
int left = 2 * i + 1; // 左子节点的索引
int right = 2 * i + 2; // 右子节点的索引
// 如果左子节点存在且大于根节点
if (left < n && arr[largest] < arr[left]) {
largest = left;
}
// 如果右子节点存在且大于目前最大的节点
if (right < n && arr[largest] < arr[right]) {
largest = right;
}
// 如果largest不是根节点
if (largest != i) {
std::swap(arr[i], arr[largest]); // 交换
// 递归堆化受影响的子树
heapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个从堆顶取出元素并调整堆
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]); // 交换堆顶和当前末尾元素
heapify(arr, i, 0); // 对新的堆顶进行堆化，注意堆的大小已减1
}
}
// 打印数组函数
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
// 主函数
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::cout << "原始数组: ";
printArray(arr);
heapSort(arr);
std::cout << "排序后的数组: ";
printArray(arr);
return 0;
}
注意事项：
1.数组索引：C++中数组索引从0开始，因此在计算子节点和父节点索引时需要特别注意。
2.堆化过程：heapify 函数是递归的，它会确保以当前节点为根的子树满足最大堆的性质。
堆排序过程：在构建完最大堆后，我们逐步将堆顶元素（最大值）与当前末尾元素交换，并减小堆的大小，然后对新的堆顶进行堆化。
3.稳定性：堆排序是不稳定的排序算法，因为相同元素的相对顺序可能会在排序过程中改变。
4.边界条件：在处理边界条件时（如子节点是否存在），需要小心确保不会访问数组之外的内存。
运行上述代码，你将看到原始数组和排序后的数组分别被打印出来。这个C++模板是一个简单而有效的堆排序实现，适用于大多数需要高效排序的场景。
八、经典例题
1.排序数组
代码题解
class Solution {
#define eleType int
#define idType int
#define maxn 50000
idType lson(idType idx){//左子节点下标
return idx*2+1;
}
idType rson(idType idx){//右子节点下标
return idx*2+2;
}
idType parent(idType idx){//父节点下标
return (idx-1)/2;
}
bool better(eleType a,eleType b){//如果是大于号就是大顶堆，否则是小顶堆
return a>b;
}
void Heapify(vector<eleType>&heap,int size,eleType curr){//堆化函数，curr代表当前节点下标
idType lsonId=lson(curr);
idType rsonId=rson(curr);
idType optId=curr;
if(lsonId<size&&better(heap[lsonId],heap[optId])){//对左右子节点判优
optId=lsonId;
}
if(rsonId<size&&better(heap[rsonId],heap[optId])){
optId=rsonId;
}
if(curr!=optId){//把大的那个子节点和当前这个节点的值进行交换
swap(heap[optId],heap[curr]);
Heapify(heap,size,optId);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
for(int i=nums.size()/2;i>=0;i--){
Heapify(nums,nums.size(),i);//从非叶子节点进行堆化操作，因为叶子节点没有子节点，这个要好好理解
}
for(int i=nums.size()-1;i>=0;i--){
swap(nums[0],nums[i]);//大顶堆的第一个元素是最大的与最后一个元素的值进行交换，也就是堆顶与叶子节点交换值
Heapify(nums,i,0);//交换值以后从第一个值再进行下沉，使它又变成大顶堆，右能找到最大值，右进行排序
}
return nums;
}
};
九、结语
学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
