堆排序详解

ゝ一纸荒年。 2022-05-26 12:15 264阅读 0赞

本文是转载文章，文章的来源：csdn博客  
博主：带鱼兄  
文章：堆排序详解  
博文地址：https://blog.csdn.net/daiyudong2020/article/details/52529791

基本概念：

要了解堆排序，首先要了解什么是堆，

要了解堆，还要先了解什么是完全二叉树。

一、什么是完全二叉树？

完全二叉树（complete binary tree）有严格的形状要求：从根节点起每一层从左到右填充。一棵高度为d的完全二叉树除了d-1层以外，每一层都是满的。底层叶节点集中在左边的若干位置上。完全二叉树如下图：

![20160913215507998][]

二、什么是堆？

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：  
a)任何一非叶节点的关键字不大于其左右孩子节点的关键字,称之为最小堆。  
b)任何一非叶节点的关键字不小于其左右孩子节点的关键字,称之为最大堆。  
由上述性质可知：  
a)最大堆的堆顶的关键字是所有关键字中最大的。  
b)最小堆的堆顶的关键字是所有关键字中最小的。  
  
通常堆是通过一维数组来实现的，在起始位置为0的情形中：  
父节点i的左子节点在位置(2\*i+1);  
父节点i的右子节点在位置(2\*i+2);  
子节点i的父节点在位置floor((i-1)/2);

一个最大堆如图：

![20160913220722172][]

三、完全二叉树怎么演变成一个堆？

给定一个整形数组a\[\]=\{7,4,2,9,8,5\}，首先将数组视为一个完全二叉树，对其进行转换成一个堆，构造初始堆是对所有的非叶节点都进行调整，从最后一个非叶节点开始调整，使其满足堆的特性。

第一步，将数组视为一个完全二叉树：

![20160913215507998][]

第二步，将完全二叉树转换成一个堆：

![20160913220754000][]![20160913220802406][]

![20160913220806375][]![20160913220809469][]

最后得到一个最大堆：

![20160913220722172][]

四、如何使用堆进行排序？

基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del\_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。所以，堆排序，最重要的两个操作就是构造初始堆和调整堆。  
  
堆排序的过程是：  
(1)建立一个堆H\[0..n-1\]。  
(2)把堆首（最大值）和堆尾互换。  
(3)把堆的尺寸缩小1，然后调整堆，目的构成新的堆。  
(4)重复步骤2，直到堆的尺寸为1。

平均時間复杂度O(nlogn)

动态图：

![20160913224824662][]

下面展示如何将一个数组a\[\]=\{7,4,2,9,8,5\}构建成堆进行排序：

第一步：构建初始堆：

![20160913220722172][]

第二步，开始排序，灰色表示被移除的堆尾（已排好序）：

![20160913222135443][]![20160913222138877][]![20160913222142787][]![20160913222154771][]![20160913222158455][]![20160913222201552][]![20160913222204506][]![20160913222207518][]![20160913222210287][]![20160913222213752][]![20160913222217990][]

五、简单例子

源码：

#include <stdio.h> /* 交换元素 */ void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; } /* 调整堆 */ void max_heapify(int arr[], int start, int end) { //建立父节点下标和子节点下标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点下标在范围內才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两個子节点大小，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子內容再继续子节点和孙节点比较 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } } } /* 堆排序 */ void heap_sort(int arr[], int len) { int i; //初始化堆，i从最后一個父节点开始调整 for (i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一個元素和已排好元素前一位做交换，再从新调整，直到排序完毕 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); max_heapify(arr, 0, i - 1); } } int main() { int arr[] = {7, 4, 2, 9, 8, 5}; int len = sizeof(arr) / sizeof(int); /* sort */ heap_sort(arr, len); /* print */ int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

编译运行：

![SouthEast][]

原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52529791][http_blog.csdn.net_daiyudong2020_article_details_52529791]

End;

[20160913215507998]: /images/20220526/e9e4fb1ab74d4c3b8010d7a00cfdf90e.png
[20160913220722172]: /images/20220526/88bf9797b00c489181f81df67250f5eb.png
[20160913220754000]: https://img-blog.csdn.net/20160913220754000
[20160913220802406]: /images/20220526/f60c5bc4458744f7904e08138a8dfbee.png
[20160913220806375]: https://img-blog.csdn.net/20160913220806375
[20160913220809469]: /images/20220526/0dd75c0446e74539a4b8dd3e4d9a4e38.png
[20160913224824662]: /images/20220526/e93cd87a7b4640bebb70feee9963a184.png
[20160913222135443]: https://img-blog.csdn.net/20160913222135443
[20160913222138877]: https://img-blog.csdn.net/20160913222138877
[20160913222142787]: https://img-blog.csdn.net/20160913222142787
[20160913222154771]: https://img-blog.csdn.net/20160913222154771
[20160913222158455]: https://img-blog.csdn.net/20160913222158455
[20160913222201552]: https://img-blog.csdn.net/20160913222201552
[20160913222204506]: https://img-blog.csdn.net/20160913222204506
[20160913222207518]: https://img-blog.csdn.net/20160913222207518
[20160913222210287]: https://img-blog.csdn.net/20160913222210287
[20160913222213752]: https://img-blog.csdn.net/20160913222213752
[20160913222217990]: /images/20220526/04c523655eab421aa69659f16b7db03b.png
[SouthEast]: /images/20220526/dfe9e27291764eceb6ef3c3b1b4a0edf.png
[http_blog.csdn.net_daiyudong2020_article_details_52529791]: http://blog.csdn.net/daiyudong2020/article/details/52529791