看懂堆排序——堆与堆排序(三) 偏执的太偏执、 2022-05-25 06:52 301阅读 0赞 # 看懂堆排序——堆与堆排序(三) # * 看懂堆排序——堆与堆排序(三) * 堆排序的基本思想 * 代码详解 * 父亲下标和孩子下标的关系 * 打印数组的函数 * 下滤函数 * 构造堆的函数 * 删除最大元函数 * 排序主函数 * 完整代码及运行截图 * 参考资料 有了前面两篇文章的铺垫, [堆与堆排序(一)][Link 1] [堆与堆排序(二)][Link 2] 我们终于可以学习“堆排序”了。 假使给定一个数组`a[N]`,其包含元素`a[0]`,`a[1]`,`a[2]`,…,`a[N-1]`,现要将其中元素按升序排列。如果利用堆这种数据结构,你会怎么做? ## 堆排序的基本思想 ## 很自然地想到,首先把此数组构造成一个小根堆(利用原来的数组,原地构造),然后依次删除最小元素,直至堆为空。为了存储每次删除的最小元素,我们需要一个额外的数组,待堆为空的时候,把额外数组的内容拷贝到原来的数组。 这种方法可行吗?当然可行。但是需要一个额外的数组,当数组很大时,这个空间开销是非常可观的。避免使用额外的数组的聪明做法是意识到这样一个事实:在每次删除最小元素之后,堆的规模缩小了1. 因此,位于堆中最后的那个单元可以用来存放刚刚删去的元素。具体来说,堆排序的步骤如下: 1. 为给定的序列创建一个堆(本文以最大堆为例) 2. 交换堆的第一个元素`a[0]`和最后一个元素`a[n-1]` 3. 堆的大小减`1`(`--n`)。如果 `n==1`,算法停止;否则,对`a[0]`进行下滤 4. 重复2~3步 ## 代码详解 ## ### 父亲下标和孩子下标的关系 ### 因为待排序的数组一般都是从0开始,而不是从1开始,所以之前讨论的父节点和孩子节点之间的关系需要修改。 之前的是: ![70][] 对于数组任一位置 `i` 上的元素,其左儿子在位置 `2i` 上,右儿子在`2i+1`上,它的父亲则在位置 ⌊i/2⌋ ⌊ i / 2 ⌋ 上。 **现在的是**: ![这里写图片描述][70 1] 对于数组任一位置 `i` 上的元素,其左儿子在位置 `2i+1` 上,右儿子在`2i+2`上,它的父亲则在位置 ⌊(i−1)/2⌋ ⌊ ( i − 1 ) / 2 ⌋ 上。 以节点 D 为例,D 的下标是 3. * `B`是它的父节点,`B`的下标是 1(= ⌊(3−1)/2⌋ ⌊ ( 3 − 1 ) / 2 ⌋ ),如图中黑色的线; * `H`是它的左孩子,`H`的下标是 7(= 2∗3\+1 2 ∗ 3 + 1 ),如图中蓝色的线; * `I`是它的右孩子,`I`的下标是 8(= 2∗3\+2 2 ∗ 3 + 2 ),如图中红色的线; 所以,我们的宏定义是: #define LEFT(i) (2*i+1) #define RIGHT(i) (2*i+2) #define PARENT(i) ((i-1)/2) ### 打印数组的函数 ### void print_array_debug(int a[], int len, int pos, char token) { for(int i=0; i<len; ++i) { if( i == pos ) { printf("%c %d ", token, a[i]); //打印元素值和记号 } else { printf("%3d ",a[i]); //正常打印 } } printf("\n\n"); } 为了展示出排序的过程,我设计了这个函数。其实这个函数和普通的打印函数差不多,无非就是多了一个在某个元素前面打印一个标记的功能。比如要在`a[0]`的前面打印一个`'*'`,那么可以这样调用(假设数组长度是10): `print_array_debug(a, 10, 0, '*');` 如果不想用它的打印标记功能,则可以给`pos`传一个负数,给`token`随便什么值都行。比如 #define DUMMY_POS -1 #define DUMMY_TOKEN '\0' 然后调用 `print_array_debug(a, 10, DUMMY_POS, DUMMY_TOKEN);` ### 下滤函数 ### 对于给定的数列,我们首先要对其进行“堆化”,堆化的方法如下: 1. 在初始化一棵包含 n 个节点的完全二叉树时,按照给定的顺序来放置键; 2. 从最后一个父母节点开始,到根为止,检查这些父母节点的键是否满足父母优势。如果该节点不满足,就把该节点的键 K 和它子女的最大键进行交换,然后再检查在新的位置上,K 是否满足父母优势。这个过程一直继续到 K 满足父母优势为止(最终它必须满足,因为对每个叶子中的键来说,这条件是自动满足的)。 **如果该节点不满足父母优势,就把该节点的键 K 和它子女的最大键进行交换,然后再检查在新的位置上,K 是否满足父母优势。这个过程一直继续到 K 满足父母优势为止——这种策略叫做下滤(percolate down)**。 // 下滤函数(递归解法) // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆 // 调整以 t 为根的子树,使之成为大根堆。 // 节点位置为 [0], [1], [2], ..., [n-1] void percolate_down_recursive(int a[], int n, int t) { int left = LEFT(t); int right = RIGHT(t); int max = t; //假设当前节点的键值最大 if(left < n) // 说明t有左孩子 { max = a[left] > a[max] ? left : max; } if(right < n) // 说明t有右孩子 { max = a[right] > a[max] ? right : max; } if(max != t) { swap(a + max, a + t); // 交换t和它的某个孩子,即t被换到了max位置 percolate_down_recursive(a, n, max); // 递归,继续考察t } } ### 构造堆的函数 ### // 自底向上建堆,下滤法 void build_max_heap(element_t a[], int n) { int i; // 从最后一个父母节点开始下滤,一直到根节点 for(i = PARENT(n); i >= 0; --i) { percolate_down_recursive(a, n, i); } } ### 删除最大元函数 ### //把最大元素和堆末尾的元素交换位置,堆的规模减1,再下滤根节点 void delete_max_to_end(int heap[], int heap_size) { if(heap_size == 2) // 当剩下2个节点的时候,交换后不用下滤 { swap( heap + 0, heap + 1 ); } else if(heap_size > 2) { swap( heap + 0, heap + heap_size - 1 ); percolate_down_recursive(heap, heap_size-1, 0); } return; } ### 排序主函数 ### void heap_sort(int a[], int length) { build_max_heap(a,length); //堆的构造 #ifdef PRINT_PROCEDURE printf("build the max heap:\n"); print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); #endif for(int size=length; size>=2; --size) //当堆的大小为1时,停止 { delete_max_to_end(a,size); #ifdef PRINT_PROCEDURE print_array_debug(a, ELMT_NUM, size-1, '|'); #endif } } ## 完整代码及运行截图 ## #include <stdio.h> #define LEFT(i) (2*i+1) #define RIGHT(i) (2*i+2) #define PARENT(i) ((i-1)/2) #define ELMT_NUM 10 #define DUMMY_POS -1 #define DUMMY_TOKEN '\0' typedef int element_t; void print_array_debug(int a[], int len, int pos, char token) { for(int i=0; i<len; ++i) { if( i == pos ) { printf("%c %d ", token, a[i]); //打印元素值和记号 } else { printf("%3d ",a[i]); //正常打印 } } printf("\n\n"); } //交换*a和*b void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 下滤函数(递归解法) // 假定以 LEFT(t) 和 RIGHT(t) 为根的子树都已经是大根堆 // 调整以 t 为根的子树,使之成为大根堆。 // 节点位置为 [0], [1], [2], ..., [n-1] void percolate_down_recursive(int a[], int n, int t) { int left = LEFT(t); int right = RIGHT(t); int max = t; //假设当前节点的键值最大 if(left < n) // 说明t有左孩子 { max = a[left] > a[max] ? left : max; } if(right < n) // 说明t有右孩子 { max = a[right] > a[max] ? right : max; } if(max != t) { swap(a + max, a + t); // 交换t和它的某个孩子,即t被换到了max位置 percolate_down_recursive(a, n, max); // 递归,继续考察t } } // 自底向上建堆,下滤法 void build_max_heap(element_t a[], int n) { int i; // 从最后一个父母节点开始下滤,一直到根节点 for(i = PARENT(n); i >= 0; --i) { percolate_down_recursive(a, n, i); } } //把最大元素和堆末尾的元素交换位置,堆的规模减1,再下滤根节点 void delete_max_to_end(int heap[], int heap_size) { if(heap_size == 2) // 当剩下2个节点的时候,交换后不用下滤 { swap( heap + 0, heap + 1 ); } else if(heap_size > 2) { swap( heap + 0, heap + heap_size - 1 ); percolate_down_recursive(heap, heap_size-1, 0); } return; } void heap_sort(int a[], int length) { build_max_heap(a,length); #ifdef PRINT_PROCEDURE printf("build the max heap:\n"); print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); #endif for(int size=length; size>=2; --size) { delete_max_to_end(a,size); #ifdef PRINT_PROCEDURE print_array_debug(a, ELMT_NUM, size-1, '|'); #endif } } int main(void) { int a[ELMT_NUM]={ 4,1,3,2,16,9,10,14,8,7}; //10个 printf("the array to be sorted:\n "); print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); heap_sort(a,ELMT_NUM); printf("sort finished:\n "); print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); } 假设文件名为`heap_sort.c`,编译: gcc heap_sort.c -DPRINT_PROCEDURE 运行结果如下图: ![这里写图片描述][70 2] 图中竖线右边的是已经有序的元素,竖线左边是堆。 【本系列完】 # 参考资料 # 【1】《数据结构与算法分析(原书第2版)》(机械工业出版社,2004) 【2】《算法设计与分析基础(第3版)》(清华大学出版社,2015) [Link 1]: https://blog.csdn.net/longintchar/article/details/80211137 [Link 2]: https://blog.csdn.net/longintchar/article/details/80219062 [70]: /images/20220525/2c62394bf0e040e18a51cedac065813f.png [70 1]: /images/20220525/8873bb23355e45e3b4f73b171b24abb4.png [70 2]: /images/20220525/d053298b03af451c96fd411b01d1cc5b.png
相关 排序-堆排序 1.堆排序前言 前面博客中讲到简单选择排序,它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知 旧城等待,/ 2022年09月30日 06:45/ 0 赞/ 241 阅读
相关 【排序】堆排序 堆的定义 设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆。 ![图示][SouthEast] 解释:如果让满足以上条件的元素序列 (k 分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 280 阅读
相关 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 堆排序的基本思想 代码详解 偏执的太偏执、/ 2022年05月25日 06:52/ 0 赞/ 302 阅读
相关 堆与堆排序(一) 堆与堆排序(一) 上一篇博文 [浅谈优先队列][Link 1] 介绍了什么是优先队列,文末提到了一种数据结构——“堆”,基于“堆”实现的优先队列,出队和入队的时间复杂度都 爱被打了一巴掌/ 2022年05月25日 01:54/ 0 赞/ 347 阅读
相关 排序——堆排序 堆排序代码 include <iostream> using namespace std; include <stdio.h> in 墨蓝/ 2022年05月21日 12:05/ 0 赞/ 271 阅读
相关 堆排序 什么是堆排序,堆排序能解决什么问题? 在排序的过程中,不能把进行排序的过程中,得一些信息保留下来吗?来加快排序的速度吗?答案是可以的。通过利用完全二叉堆的结构来保留信息。 迷南。/ 2021年10月29日 07:20/ 0 赞/ 380 阅读
相关 堆和堆排序 堆排序 堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复 杂度均为 O(nlogn),它也 柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 414 阅读
相关 堆排序 文章目录 一、堆排序介绍 二、如何进行堆排序 一、堆排序介绍 百度百科: 堆排序(Heapsort)是指利用堆积树 我会带着你远行/ 2021年10月18日 16:46/ 0 赞/ 366 阅读
相关 排序-堆排序 [2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆: 先看下图(来源 清疚/ 2021年09月20日 03:22/ 0 赞/ 449 阅读
相关 堆排序 堆排序的特点是:在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中父结点和子结点之间的内在关系,在当前无序区中选择关键字最大(或最小) 不念不忘少年蓝@/ 2021年09月17日 00:16/ 0 赞/ 471 阅读
还没有评论,来说两句吧...