堆排序算法详解：从原理到代码实现

堆排序算法详解：从原理到代码实现

引用

CSDN

1.

https://m.blog.csdn.net/2301_79090563/article/details/143462495

文章目录

• 前言
• 1.建堆方法的选择
• 2.优先使用向下调整的原因
• 3.堆排序图解（大堆-升序为例子）
• 3.1 向下调整法-建大堆
• 3.2 进行堆排序
• 4.堆排序代码
• 4.1 向下调整法
• 4.1. 1 小堆
• 4.1. 2 大堆
• 4.2 堆排序
• 5. 关于小堆——降序
• 6.性能分析

前言

堆排序是一种基于二叉堆的数据结构的排序算法。它利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大顶堆和小顶堆，是完全二叉树。

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)，堆排序是原地排序，不需要额外的存储空间。
稳定性：堆排序是不稳定的排序算法，相同的元素可能在排序后改变相对顺序。
适用性：由于堆排序是原地排序，适用于空间受限的情况。同时，它也适用于大数据量的排序。