四、(1)堆排序
第一次听堆排序是在107lab听忠哥讲的,但是没讲怎么实现。那时刚看了数据结构的二叉树,还以为要通过指针建立二叉树的方式来实现,觉得挺难的。
其实堆排序实现没有想象中的那么难。
“堆”这个词最初是在堆排序中提出来的,但后来就逐渐指”废料收集储存区“,就像程序设计语言Lisp和Java中所提供的设施那样。我们这里的堆数据结构不是废料收集存储区。
堆排序的运行时间与归并排序一样为O(n lg n), 但是一种原地(in place)排序。
(二叉)堆数据结构是一种数组对象,它可以被视为一棵完全二叉树。
对于一个数组arr[ ]={16,14,10,8,7,9,3,2,4,1}的存储数据结构如下图:
在这个结构中,对于每一个根节点i ,要保证它都比他的子节点大
我们可以用一个数组A【1...length【A】】来表示这个完全二叉树结构。 其中A【1】为根节点1
首先问题是求父节点、左儿子、右儿子的坐标,通过观察我们可以用宏或者内联函数实现:
-
-
inlineintParent(inti){returni>>1;}
-
inlineintLeft(inti){returni<<1;}
-
inlineintRight(inti){return(i<<1)|1;}
无论是《C++ primer》还是《Effective C++》,都讲过宏的缺陷,用内联函数是个更好的选择。位运算做乘除的速度更快。
至于算法演示过程在《算法导论》上讲得很详细,不再赘述。
堆排序过程需要以下三个函数:
1、Max-Heapify(A,i): 保持堆的性质,让A【i】在最大堆中“下降”,使以i节点为根的字数成为最大树
2、Buid-Max-Heap(A):自底向上将数组A【1...n】变成一个最大堆
3、Heap-Sort(A): 进行堆排序
C++代码实现:(数组A是下标1开始的)
-
-
#include<cstdio>
-
#include<algorithm>
-
usingnamespacestd;
-
-
-
-
inlineintParent(inti){returni>>1;}
-
inlineintLeft(inti){returni<<1;}
-
inlineintRight(inti){return(i<<1)|1;}
-
-
-
inlinevoidSwap(int&a,int&b){if(a!=b){a^=b;b^=a;a^=b;}}
-
-
-
-
-
-
-
-
-
-
-
-
-
voidMaxHeap(int*A,intheap_size,inti){
-
-
intl,r,max;
-
l=Left(i);
-
r=Right(i);
-
-
if(l<=heap_size&&A[l]>A[i])
-
max=l;
-
else
-
max=i;
-
-
if(r<=heap_size&&A[r]>A[max])
-
max=r;
-
-
if(max!=i){
-
Swap(A[i],A[max]);
-
MaxHeap(A,heap_size,max);
-
}
-
}
-
-
-
voidBuidMaxHeap(int*A,intheap_size){
-
-
for(inti=heap_size>>1;i>=1;--i){
-
MaxHeap(A,heap_size,i);
-
}
-
}
-
-
-
voidHeapSort(int*A,intheap_size){
-
-
BuidMaxHeap(A,heap_size);
-
intlen=heap_size;
-
for(inti=heap_size;i>=2;--i){
-
Swap(A[1],A[i]);
-
--len;
-
MaxHeap(A,len,1);
-
}
-
}
(2)优先级队列
C++ STL中的priority_queue就是用这种方法来实现的。
1、Heap-MaxiNum(A): 取出堆中的最大值
2、Heap-Extract-Max(A):删除堆中的最大值并返回它的值
3、Heap-Increase-Key(A,i,key):将节点i的值增加到key,这里key要比i节点原来的数大。
4、Max-Heap-Insert(A, key): 插入一个新元素key到堆中,要用到3的函数
C++实现:
-
-
-
intHeapMaxNum(int*A){
-
returnA[1];
-
}
-
-
intHeapExtractMax(int*A,intheap_size){
-
if(heap_size>=1){
-
intmax=A[1];
-
A[1]=A[heap_size];
-
--heap_size;
-
MaxHeap(A,heap_size,1);
-
returnmax;
-
}
-
}
-
-
boolHeapIncreaseKey(int*A,inti,intkey){
-
if(key<A[i])
-
returnfalse;
-
A[i]=key;
-
while(i>1&&A[Parent(i)]<A[i]){
-
Swap(A[i],A[Parent(i)]);
-
i=Parent(i);
-
}
-
returntrue;
-
}
-
-
voidMaxHeapInsert(int*A,intkey,intheap_size){
-
++heap_size;
-
A[heap_size]=-2147484646;
-
HeapIncreaseKey(A,heap_size,key);
-
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
自学算法导论中前几章,并自己...二、快速排序、分治法排序、堆排序 http://blog.csdn.net/ceofit/article/details/7442874 三、计数排序、基数排序、桶排序 http://blog.csdn.net/ceofit/article/details/7447547 ...
算法导论上的堆排序c++源程序||学习分享
参考《算法导论》这本书写的一个堆排序的代码,我个人是用Visual studio写的。只要一个积分哦
算法导论 快速排序 堆排序 算法导论上的算法实现更加精简高效 代码可编译运行测试 加了测试用例 加了注释
实现算法导论中的堆排序,区别数组以0作为根,算法导论中的实现是以数组1作为根
算法导论中第二章所有排序的自己模拟,快速排序,堆排序,计数排序,最大最小数,选择第n个数等等
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第一章到第八章重要...堆排序 快速排序(2中分割方法) 随机化快速排序 TAIL-RECURSIVE-QUICKSORT Counting sort Radix sort 二分法搜索
第6章 堆排序 第7章 快速排序 第8章 线性时间排序 第9章 中位数和顺序统计学 第三部分 数据结构 第10章 基本数据结构 第11章 散列表 第12章 二叉查找树 第13章 红黑树 第14章 数据结构的扩张 第四部分 高级设计和...
php堆排序(算法导论)
ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算在排序中。 for(int i = length; i >= 2;) { temp = A[i]; //交换堆的第一个元素和堆的最后一个元素 A[i] = A[1]; A[1] = temp; i--; //...
算法导论第三版第六章内容,作者使用C#与C++两种编程语言实现
上个资源的有效排序下标是由1开始的,0只做了填充作用,这次则由下标0为根节点: for(int i = length; i >= 1;) //最后一个肯定是最小的 { temp = A[i]; //交换堆的第一个元素和堆的最后一个元素 A[i] = A[0]; ...
算法导论上堆排序算法的vc6.0下的Test实例。
第六章 堆排序(Heapsort) 第七章 快速排序(Quicksort) 第八章 线性时间中的排序(Sorting in Linear Time) 第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构...
•移除两章很少讲授的内容:二项堆和排序网络。 •修订了动态规划和贪心算法相关内容。 •流网络相关材料现在基于边上的全部流。 •由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占...
根据算法导论第六章实现的堆排序
包括源码:常用排序算法(插入、堆、归并、快速)、装配线问题、最长公共子序列问题、矩阵连乘问题、 优先队列、huffman编码、贪心算法,全部用Java实现的。 算法导论答案
3、移除两章很少讲授的内容:二项堆和排序网络。 4、修订了动态规划和贪心算法相关内容。 5、流网络相关材料现在基于边上的全部流。 6、由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所...
这些代码是对算法导论上对排序部分的总结,实现了以下排序方法:插入排序,合并排序,堆排序,快速排序,计数排序,每种实现都有详细的注释和相应的测试程序,可查找http://blog.csdn.net/china8848<br>中对相关问题...
移除两章很少讲授的内容:二项堆和排序网络。 修订了动态规划和贪心算法相关内容。 流网络相关材料现在基于边上的全部流。 由于关于矩阵基础和strassen算法的材料移到了其他章,矩阵运算这一章的内容所占...