数据结构与算法 (28).pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构与算法 (28).pdf》由会员分享,可在线阅读,更多相关《数据结构与算法 (28).pdf(28页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、9.1 二叉排序树9.2 二叉平衡树9.3 堆和堆排序第9章 基于二叉树的查找与排序 9.3.1 堆和堆排序的概念9.3.2 堆的调整9.3.3 建堆9.3.4 堆排序9.3 堆和堆排序 堆的定义若n个元素的序列a1a2 an 满足ai a2i 或或ai a2iai a2i+1ai a2i+1则分别称该序列则分别称该序列aa1 1a a2 2 a an n 为为小根堆小根堆 或或大根堆。大根堆。从堆的定义可以看出从堆的定义可以看出,堆实质是满足双亲节点堆实质是满足双亲节点大于大于(或小于或小于)孩子节点性质的完全二叉树孩子节点性质的完全二叉树42212403034365041小根(顶)堆122
2、23440303650410 1 2 3 4 5 6 7 8 小根堆例子55087403036341222大根(顶)堆87503640303412220 1 2 3 4 5 6 7 8 大根堆例子【例例】下面序列为堆,对应的完全二叉树分别为:9877356255143548(a)一个大根堆1448356255983577(b)一个小根堆9877 35 62 55 14 35 4814 48 35 62 55 98 35 779877356255143548(a)一个大根堆1448356255983577(b)一个小根堆若在输出堆顶的最小值若在输出堆顶的最小值(最大值最大值)后后,使得剩使得剩余
3、余n n-1 1个元素的序列重又建成一个堆个元素的序列重又建成一个堆,则得到则得到n n个个元素的次小值元素的次小值(次大值次大值)如此反复如此反复,便能得便能得到一个有序序列到一个有序序列,这个过程称之为这个过程称之为堆排序堆排序。堆排序85087403036341222502240303634128787503640303412222250364030341287 利用大根堆进行排序的示例演示实现堆排序需解决两个问题:实现堆排序需解决两个问题:1、如何由一个无序序列建成一个堆?2、如何在输出堆顶元素后,调整剩余元素为一个新的堆?下面先讨论第二个问题:下面先讨论第二个问题:9.3.1 堆和堆
4、排序的概念 9.3.2 堆的调整9.3.3 建堆9.3.4 堆排序9.3 堆和堆排序如何在输出堆顶元素后,调整剩余元素为一个如何在输出堆顶元素后,调整剩余元素为一个新的堆?新的堆?解决方法:从堆顶至叶子解决方法:从堆顶至叶子“筛选”“筛选”输出堆顶元素之后,以堆中最后一个元素替代输出堆顶元素之后,以堆中最后一个元素替代之;之;然后将根结点值与左、右子树的根结点值进行然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;比较,并与其中小者进行交换;重复上述操作,直至叶子结点,或一次比较过重复上述操作,直至叶子结点,或一次比较过程中没有交换,将得到新的堆程中没有交换,将得到新的堆13
5、3827497665499713输出根并以最后一个元素代替之;比较其左右孩子值的大小,并与其中较小者交换;9727974997小根堆typedef struct node ElementType*data;/*存储元素的数组存储元素的数组*/int Size;/*堆中当前元素个数堆中当前元素个数*/Hnode,*Heap;/*堆的类型定义堆的类型定义*/堆的类型定义void HeapAdjust(Heap H,int s,int m)/*下滤:将下滤:将H中以中以H-Datap为根的子堆调整为最大堆为根的子堆调整为最大堆*/int Parent,Child;ElementType X;X=H-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法 28 数据结构 算法 28
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内