堆排序创建

灰太狼 2024-04-06 14:40 61阅读 0赞

#### 堆排序创建 ####

*  一、介绍
 *   *  1、什么是堆
     *  2、大项堆（排序前）
     *  3、小项堆（排序前）
     *  4、排序思想
 *  二、大项堆排序案例
 *   *  1、流程
     *  2、讲解
 *  三、总结

--------------------

## 一、介绍 ##

### 1、什么是堆 ###

堆是一种叫做完全二叉树的数据结构，可以分为大项堆，小项堆，而堆排序就是基于这种结构而产生的一种程序算法。

### 2、大项堆（排序前） ###

大项堆:每个节点的值都大于或者等于他的左右孩子节点的值  
![在这里插入图片描述][1eb447601e5d4c1ab08af8d4612f50ad.png]

### 3、小项堆（排序前） ###

小项堆:每个结点的值都小于或等于其左孩子和右孩子结点的值  
![在这里插入图片描述][1ffbc197510248578237bcdcce2dbdf7.png]

### 4、排序思想 ###

父–>子:i—>左孩子:2*i+1, 右孩子:2*i+2;  
子–>父:i—>(i-1)/2; (i为下标元素)

1.  首先将待排序的数组构造成一个大项堆，此时，整个数组的最大值就是堆结构的顶端
2.  将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.  将剩余的n-1个数再构造成大项堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意:升序用大项堆，降序就用小项堆(默认为升序)

## 二、大项堆排序案例 ##

### 1、流程 ###

1.  从最后一棵子树开始,从后往前调整
2.  每次调整,从上往下调整
3.  调整为大根堆

### 2、讲解 ###

首先我们给定一个无序的序列，将其看做一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。  
![在这里插入图片描述][a24cb65a7da54803812a3c3e75be1955.png]

在这里1小于最大值子节点9，则交换1和9的位置  
![在这里插入图片描述][24876d8c934e45da96d8539eeafec288.png]

找到下一个非叶子节点3，用它和它的左右子节点进行比较，3小于最大值子节点9，交换3和9位置  
![在这里插入图片描述][41a123b33bc04edf85a4ff10ebb55358.png]  
此时发现3小于6这个最大值子节点，我们需要进行调整，因此交换6和3的位置  
![在这里插入图片描述][8b16ce94b91b4037b3a454505f51013a.png]  
**此时我们就构造出来一个大根堆,下来进行排序**  
首先将顶点元素9与末尾元素3交换位置，此时末尾数字为最大值。排除已经确定的最大元素，将剩下元素重新构建大根堆  
**一次交换重构如图:**  
![在这里插入图片描述][43f6c174d71249928e07db80648879d4.png]

**最终排序结果:**  
![在这里插入图片描述][0e460974e3e9495fb669dd2eb4f44667.png]

## 三、总结 ##

由此，我们可以归纳出堆排序算法的步骤：

1.  把无序数组构建成二叉堆。
2.  循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

堆排序是不稳定的排序，空间复杂度为O(1),平均的时间复杂度为O(nlogn),最坏情况下也稳定在O(nlogn)

[1eb447601e5d4c1ab08af8d4612f50ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/bd4b99e2829446b5917361b20e4e579d.png
[1ffbc197510248578237bcdcce2dbdf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2eabc7b5b7af41018337bb2a350a58bf.png
[a24cb65a7da54803812a3c3e75be1955.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/ba3785030c1d4ecab70ec9951ea2eb3a.png
[24876d8c934e45da96d8539eeafec288.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c33b2f70bc294c31a0e529466b723f5a.png
[41a123b33bc04edf85a4ff10ebb55358.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a858a1d8d39e473ea1a4fdff7447a957.png
[8b16ce94b91b4037b3a454505f51013a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c77e6bf4a572499aa254ad2214b5cea6.png
[43f6c174d71249928e07db80648879d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/9c9610aff77e4948b67534d1b3aba68f.png
[0e460974e3e9495fb669dd2eb4f44667.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/61741f6fb60f49758f27b9b7169df2e8.png