文章目录
前言1.建堆方法的选择2.优先使用向下调整的原因3.堆排序图解（大堆-升序为例子）3.1 向下调整法-建大堆3.2 进行堆排序
4.堆排序代码4.1 向下调整法4.1. 1 小堆4.1. 2 大堆4.2 堆排序
5. 关于小堆——降序6.性能分析
前言
🐱个人主页： 代码探秘者 🐭C语言专栏：C语言 🐰C++专栏： C++ / STL使用以及模拟实现/C++11新特性 🐹数据结构专栏： 数据结构 / 十大排序算法 🐶 Linux专栏： Linux系统编程 / Linux网络编程（准备更新） 🌈喜欢的诗句:天行健,君子以自强不息.
1.建堆方法的选择
(1). 建堆 升序：建大堆 降序：建小堆
(2). 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
2.优先使用向下调整的原因
对于最大堆，理论上可以采用向上调整的方法来构建，但实际上并不常用。
这是因为向上调整的方法在构建最大堆时效率较低，时间复杂度为O(nlogn)，与直接插入法相同，而向下调整（堆化）的方法时间复杂度为O(n)，更为高效。
为什么向上调整不常用：
效率问题：如前所述，向上调整建堆的时间复杂度为O(nlogn)，而向下调整建堆的时间复杂度为O(n)。在构建堆时，我们通常希望尽可能高效，因此更倾向于使用向下调整的方法。
操作复杂性：向上调整需要在每次插入新元素后，将新元素与其父节点比较并可能进行交换，直到它找到合适的位置。这个过程涉及到多次的比较和交换，操作相对复杂。
堆的性质：在最大堆中，我们希望较大的值靠近根节点，而较小的值靠近叶子节点。向下调整的方法更自然地符合这一性质，因为它从最后一个非叶子节点开始，逐个向下调整，直到根节点。
3.堆排序图解（大堆-升序为例子）
3.1 向下调整法-建大堆
原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：
(1) 选最后一个非叶子结点
（2）逐个向下调整，直到根节点
3.2 进行堆排序
建好大堆（用我们刚刚上面的从最后一个非叶子结点，从下往上，一直到根结点，进行向下调整法）把根节点和最后一个结点交换（这样最大的不就放最后了嘛）
然后从根节点(堆顶)，又继续向下调整 这样20是最大的，就排好在最后了
之后交换5和17
然后向下调整，这样排好17,交换3和16
交换好，然后向下调整，继续交换5和4，调整后，
交换4和3，然后调整
这样就完成了！
4.堆排序代码
4.1 向下调整法
4.1. 1 小堆
我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。
选出最小的孩子最小孩子比父亲小，就交换上来更新parent和minchild，一直循环到最后
//向下调整:从哪里开始
//删除调用
void AdjustDown(DataType* a, int n, int parent)
{
//先找到最小的孩子
int minchild = 2 * parent + 1; //假设左孩子最小
while (minchild < n)
{
//右孩子存在，而且小于左孩子
if (minchild + 1 < n && a[minchild + 1] < a[minchild])
{
minchild++; //更新最小为右孩子
}
//开始向下调整
//小堆为例)
if (a[minchild] < a[parent])
{
Swap(&a[minchild], &a[parent]); //交换
//更新parent和minchild
parent = minchild;
minchild = 2 * parent + 1;
}
else
{
break;
}
}
}
4.1. 2 大堆
选出最大的孩子最大孩子比父亲大，就交换上来更新parent和minchild，一直循环到最后
//向下调整: 从哪里开始
//删除调用
void AdjustDown(DataType* a, int n, int parent)
{
//先找到最大的孩子
int maxchild = 2 * parent + 1; //假设左孩子最小
while (maxchild < n)
{
//右孩子存在，而且大于左孩子
if (maxchild + 1 < n && a[maxchild+ 1] > a[maxchild])
{
maxchild++; //更新最大为右孩子
}
//开始向下调整
//大堆为例
if (a[maxchild] > a[parent])
{
Swap(&a[maxchild], &a[parent]); //交换
//更新parent和minchild
parent = maxchild;
maxchild = 2 * parent + 1;
}
else
{
break;
}
}
}
4.2 堆排序
//交换
void Swap(DataType* px, DataType* py)
{
DataType tmp = *px;
*px =*py;
*py = tmp;
}
void HeapSort(int* a, int n)
{
//向上调整建堆 不推荐nlogn
// for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i); //调用向下调整法
}
//堆排序
//开始：堆顶和最后一个元素交换
int end = n - 1;
while (end > 0)
{
//之后：堆顶和没有排好的最后一个元素交换
Swap(&a[0], &a[end]);
//从根结点开始向下调整
AdjustDown(a, end, 0);
--end; //排好一个
}
}
void HeapSortTest()
{
int a[] = { 50,100,70,65,60,32 };
int n = sizeof(a) / sizeof(a[0]);
HeapSort(a, n);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
5. 关于小堆——降序
把向下调整建大堆，该成建小堆
其他步骤差不多
6.性能分析
时间复杂度：O(n log n)，其中n是数组的长度。
空间复杂度：O(1)，堆排序是原地排序，不需要额外的存储空间。
稳定性：堆排序是不稳定的排序算法，相同的元素可能在排序后改变相对顺序。
适用性：由于堆排序是原地排序，适用于空间受限的情况。同时，它也适用于大数据量的排序。