堆调整函数解决的问题是:当除了堆顶以外的元素都满足堆的条件,如何调整堆顶元素,使整个序列满足堆的条件。堆的条件,是啥?其实堆是棵二叉树,满足父节点的数值比两个儿子节点的数值大。那么如何解决上述问题呢?思路也很简单:将父节点与两个儿子节点比较,找到最大的那个,放到堆顶,将原来堆顶元素放到最大元素的原来位置,然后对这颗子树递归调用堆调整函数。
更一般地说,对于堆中第i个节点,如何调整堆中的元素,满足堆的条件?代码如下:
void MaxHeapfy (int Array[], int i, int iHeapSize) //MaxHeapfy表示维护一个最大堆
{
intl = 2 * i + 1; // 定位到i的左儿子,为啥这样定位?请翻书看下堆的数组存储
int r = 2 * i + 2; // 定位到i的右儿子
int iMax;
// 这段代码有意思,有看头,其功能是比较元素i和他的两个儿子,找到其中最大的那个,将他的位置记录到iMax中。
// 为啥左儿子的判断既有if又有else,右儿子不用?每个判断都有两个条件,前面是递归是否终止,后面是比较大小。何时、哪个条件不满足,会跳出if条件?这个地方想着简单,不过写的时候,debug了一会儿,才把代码写对。个中细节,还是debug的时候体会吧。
if (l < iHeapSize && Array[l] > Array[i])
iMax = l;
else
iMax = i;
if (r < iHeapSize && Array[r] > Array[iMax])
iMax = r;
if (iMax != i) // 如果堆顶已经是最大元素,则不用调整了,否则,交换堆顶与iMax位置的元素
{
int iTemp; // 交换元素
iTemp = Array[i];
Array[i] = Array[iMax];
Array[iMax] = iTemp;
MaxHeapfy (iMax, iHeapSize); // 递归,对子树重新建立堆
}
}
思路和代码都很简单,需要细想一想的地方就是上面“有看头”的那部分代码。难点主要在于,将选取三个数的最大者与递归终止条件混在一起判断了。
利用上面的调整函数,建立堆就很容易了。堆是用数组存储的,越往后,越是底层节点;接上文,父节点和儿子节点的关系可以用l = 2 * i + 1和l = 2 * i + 2;计算。树是从底向上建立的,倒数第二层节点的位置在数组的中部,就从这里开始。代码如下:
void BuildMaxHeap (int Array[], int iHeapSize)
{
if (iHeapSize <= 1) // 防御性代码
return;
int i = iHeapSize / 2; // 定位到数组中间,这部分是叶子节点的上一层,在此基础上建立二叉树(叶子节点自身就是二叉树了)
for (int j=i; j>=0; j--) // 从后向前遍历
MaxHeapfy (j, iHeapSize); // 自底向上建立堆,直到堆顶(位于数组最前端)
}
好,完事。
分享到:
相关推荐
1.对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; 2.待排序表的表长不小于100,表中数据随机产生,至少用5组不同的数据作比较,比较指标有:关键字比较次数和关键字移动次数...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
本份资源包含本科数据结构各种排序代码,如快排,堆排等代码实现(C/C++),同时本代码可直接进行运行查看结果,欢迎各位朋友下载.
去做经过的时间,gnuplot,graphviz 堆排序 vs 合并排序 vs 快速排序优先队列桶排序订单统计开放散列霍夫曼编码Dijkstra 算法矩阵链乘法最长公共序列最近的点对收费公路重建张开的树其他待办事项包括覆盖代码贪心...
MATLAB代码设计路径 openWHURS 关于本仓库 本仓库提供武汉大学遥感信息工程学院(School of ...一个采用堆排序优化的最短路径程序。By Xiang Zheng By Wei Yu By Chen Dingzhi By Chen Dingzhi & Ma
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析...
10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4...
作 者:严蔚敏 李冬梅 吴伟民 出版时间:2011-2-1 0:00:00 ...8.4.2 堆排序 221 8.5 归并排序 226 8.6 基数排序 228 8.6.1 多关键字的排序 228 8.6.2 链式基数排序 228 8.7 小结 232 习题 233
10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论 第11章 外部排序 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 ...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
移除两章很少讲授的内容:二项堆和排序网络 修订了动态规划和贪心算法相关内容 流网络相关材料现在基于边上的全部流 由于关于矩阵基础和Strassen算法的材料移到了其他章 矩阵运算这一章的内容所占篇幅更小 修改...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...