第八章 排序 七、堆排序

目录

一、堆的概念

1、大根堆

2、小根堆

二、建立大根堆

1、举个例子，我们要让一个序列变换成为一个大根堆

2、我们把序列看成一棵完全二叉树，而完全二叉树有以下特性：

3、在此序列中，由于是从1开始的序列，所以分支结点为1到4

4、我们从后往前检查，首先就检查下标为4的结点09

5、下一个检查结点78，通过比较发现87为更大的孩子，于是进行互换

6、继续检查结点17，通过比较发现45为更大的孩子，于是进行互换

7、之后检查结点53，通过比较发现87为更大的孩子，于是进行互换

8、最后再次检查结点53，通过比较发现78为更大的孩子，于是进行互换

9、最终我们得到了一个大根堆

三、建立大根堆的代码实现

四、堆排序算法思想

五、例子

1、我们有如下序列，我们要将此序列使用堆排序进行升序排序

2、让序列首尾元素互换，如此一来，我们就将最大元素放到了队尾。

3、可是现在的序列又失去了大根堆的特性，所以我们要重新将它化为大根堆，只是这次我们要把87排除在外，因为它已经排好序了

4、这次我们又让序列中的首尾元素互换，也就是78和53，将第二大的元素找到

5、再次进行大根堆化

6、再次首尾互换

7、经历n-1次处理，就能得到最终的升序序列

六、代码实现

七、验证

八、算法效率分析

九、稳定性

十、总结

---

一、堆的概念

1、大根堆

简单来说，大根堆就是根结点均大于它的左右孩子结点的一棵完全二叉树

2、小根堆

同样的，对与小根堆来说，它就是根结点均小于它的左右孩子结点的一棵完全二叉树

二、建立大根堆

1、举个例子，我们要让一个序列变换成为一个大根堆

2、我们把序列看成一棵完全二叉树，而完全二叉树有以下特性：

1. 分支结点的下标为[0 到 ]
2. 若一个结点的下标为i，则它的左孩子下标为2i，右孩子下标为2i-1，父节点的下标为.

3、在此序列中，由于是从1开始的序列，所以分支结点为1到4

我们要检查每个分支结点的左右孩子是否满足大根堆的特性，根>=左右。

4、我们从后往前检查，首先就检查下标为4的结点09

它的左孩子为32，无右孩子，而且32大于9，不满足大根堆的特性，所以让9和32互换，若左右孩子都更大，则取更大的那个。

5、下一个检查结点78，通过比较发现87为更大的孩子，于是进行互换

互换后为下图

6、继续检查结点17，通过比较发现45为更大的孩子，于是进行互换

互换后为下图

7、之后检查结点53，通过比较发现87为更大的孩子，于是进行互换

互换后为下图

但是互换后又有新的问题出现了，以53为根的子树再次不满足大根堆的特性，于是我们要继续互换。（小元素不断”下坠“）

8、最后再次检查结点53，通过比较发现78为更大的孩子，于是进行互换

9、最终我们得到了一个大根堆

三、建立大根堆的代码实现

void HeadAdjust(int a[],int k,int len){//k是分支结点的边界
    a[0] = a[k];//将分支结点存在下标为0的地方
    for (int i = 2*k; i <= len; i*=2) {//检查左孩子
        if (i1]){//找到更大的孩子
            i++;
        }
        if(a[0]>=a[i]){//满足大根堆特性
            break;
        }else{//不满足就交换
            a[k] = a[i];
            k = i;
        }
    }
    a[k] = a[0];
}
 
void BuildMaxHeap(int a[],int len){
    for (int i = len/2; i > 0; i--) {//遍历所有的分支结点
        HeadAdjust(a,i,len);//调用函数对序列进行大根堆化
    }
}

四、堆排序算法思想

每次都将大根堆的序列第一个元素和序列最后一个元素互换。

五、例子

1、我们有如下序列，我们要将此序列使用堆排序进行升序排序

2、让序列首尾元素互换，如此一来，我们就将最大元素放到了队尾。

3、可是现在的序列又失去了大根堆的特性，所以我们要重新将它化为大根堆，只是这次我们要把87排除在外，因为它已经排好序了

4、这次我们又让序列中的首尾元素互换，也就是78和53，将第二大的元素找到

5、再次进行大根堆化

6、再次首尾互换

7、经历n-1次处理，就能得到最终的升序序列

六、代码实现

#include "bits/stdc++.h"
using namespace std;
 
void HeadAdjust(int a[],int k,int len){//k是分支结点的边界
    a[0] = a[k];//将分支结点存在下标为0的地方
    for (int i = 2*k; i <= len; i*=2) {//检查左孩子
        if (i1]){//如果该分支结点满足大根堆的特性
            i++;//就检查下一个分支结点
        }
        if(a[0]>=a[i]){//满足大根堆特性
            break;
        }else{//交换
            a[k] = a[i];
            k = i;
        }
    }
    a[k] = a[0];
}
 
void BuildMaxHeap(int a[],int len){
    for (int i = len/2; i > 0; i--) {//遍历所有的分支结点
        HeadAdjust(a,i,len);//调用函数对序列进行大根堆化
    }
}
 
void HeapSort(int a[],int len){
    BuildMaxHeap(a,len);//建立大根堆
    for (int i = len; i > 1; i--) {//进行n-1次处理
        int temp = a[1];//首尾交换
        a[1] = a[i];
        a[i] = temp;
        HeadAdjust(a,1,i-1);//每次首位交换后都要检查是否为大根堆
    }
}
 
 
int main(){
    int count,arr[10];
    scanf("%d",&count);//输入数组长度
    for (int i = 1; i <= count; ++i) {
        scanf("%d",&arr[i]);//输入数组
    }
    HeapSort(arr,count);//调用排序函数
    for (int i = 1; i <= count; ++i) {
        printf("%d ",arr[i]);//输出数组
    }
    return 0;
}

七、验证

八、算法效率分析

一个结点，每“下坠”一层，最多只需对比关键字2次。

若树高为h，某结点在第i层，则将这个结点向下调整最多只需要“下坠” h-i层，关键字对比次数不超过2(h-i)

建堆的时间复杂度

总的时间复杂度和空间复杂度

九、稳定性

堆排序是不稳定的

十、总结