1、 堆排序定义
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
注意:
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
/*
堆排序
(1)用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,
由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys,
同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。
堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前,
且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
*/
#include <iostream>
//生成大根堆
void HeapAdjust(int SortData[],int StartIndex, int Length)
{
while(2*StartIndex+1 < Length)
{
int MinChildrenIndex = 2*StartIndex+1 ;
if(2*StartIndex+2 < Length )
{
//比较左子树和右子树,记录最大值的Index
if(SortData[2*StartIndex+1]<SortData[2*StartIndex+2])
{
MinChildrenIndex = 2*StartIndex+2;
}
}
if(SortData[StartIndex] < SortData[MinChildrenIndex])
{
//交换i与MinChildrenIndex的数据
int tmpData =SortData[StartIndex];
SortData[StartIndex] =SortData[MinChildrenIndex];
SortData[MinChildrenIndex] =tmpData;
//堆被破坏,需要重新调整
StartIndex = MinChildrenIndex ;
}
else
{
//比较左右孩子均大则堆未破坏,不再需要调整
break;
}
}
return;
}
//堆排序
void HeapSortData(int SortData[], int Length)
{
int i=0;
//将Hr[0,Lenght-1]建成大根堆
for (i=Length/2-1; i>=0; i--)
{
HeapAdjust(SortData, i, Length);
}
for (i=Length-1; i>0; i--)
{
//与最后一个记录交换
int tmpData =SortData[0];
SortData[0] =SortData[i];
SortData[i] =tmpData;
//将H.r[0..i]重新调整为大根堆
HeapAdjust(SortData, 0, i);
}
return;
}
//TestCase
int main()
{
int SortData[] ={12,36,24,85,47,30,53,91};
HeapSortData(SortData, 8);
for (int i=0; i<8; i++)
{
std::cout<<SortData[i]<<" ";
}
std::cout<<std::endl;
return 0;
}
原文网址:
http://www.maycode.com/index.php/hotspot/27-clanguage/1123-cpp.html
分享到:
相关推荐
堆排序算法C语言程序,亲测可用,堆排序算法是基于选择排序算法思想,利用堆结构和二叉树的一些性质来完成数据的排序。
堆排序的源程序--编译、运行成功的。 其基本算法思想参照《算法导论》。 有点编译器需去掉-system("pause");
分治思想的排序包括:归并排序,快速排序,堆排序。 程序把随机生成的整数进行排序,开始时用1到7选择用哪种排序(没有图形界面,算法为主),堆排序较为特殊,见注释。 有问题到博客中该篇文章下欢迎反馈交流~
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 【基本要求】 (1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数...
堆排序(C语言实现)算法思想步骤程序 算法思想 见: 4. 选择排序—堆排序(Heap Sort) 算法导论——堆排序heapsort 步骤 1. 将n个元素建立初始堆,第一个节点放在数组下标1中,因此n个节点对应数组 a[1] ~ a[n],...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
// 堆排序 //HeapSort( a ); // 归并排序 //MergeSort( a ); // 基数排序 { SLList b; int i; b.keynum = 3, b.recnum = LENGTH;// 对3位整数进行基数排序 for ( i = 1; i ; i++ ) { b.r[i]....
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
1.排序算法:常见的排序算法包括冒泡排序、选择排序、插入排序、 归并排序等,需要熟练掌握其原理、时间复杂度及实现方法。 2.搜索算法:包括深度优先搜索(DFS)和广度优先搜索(BFS),在 图论、树的遍历等场景下...
4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序算法示例 126 4.9 排序算法的效率 129 4.10 排序算法的其他应用 130 4.10.1 反序排序 130 4.10.2 字符串数组的排序 132...
一大堆模版 自己可以下来参考 应该有200个以上吧 自己下来看看 其中一个目录 图论 路径问题 0/1边权最短路径 BFS 非负边权最短路径(Dijkstra) ... 堆排序 归并排序(OK) 基数排序 拓扑排序 排序网络
快速排序算法 ……………………… 算法基本思想及实现 …………… 算法的性能 ……………………… 随机快速排序算法 ……………… 非递归快速排序算法 …………… 三数取中划分算法 ……………… 三划分快速排序算法...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 2.4运行环境 (1)WINDOWSXP系统 (2)C++ 编译环境 3.实验方法 本实验主要是内排序,通过比较的次数和移动的次数判断排序的好坏。...
《算法引论:一种创造性方法》是国际算法大师乌迪....书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性...
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。 9.标准...
易语言官方支持库以及网上流传的很多模块中的很多命令或...当前已支持算法:快速排序、插入排序、堆排序、归并排序、取最大、取最小、向下取整、向上取整、反转字节集、反转文本、反转数组、扩展欧几里得、中国剩余定
讨论并比较所有通用的排序算法。对以下四种算法详细地进行了分析:插入排序、希尔排序、堆排序以及快速排序。堆排序平均情形运行时间的分析对于这一版来说是新的内容。本章末尾讨论了外部排序。 第8章讨论不相交集...
9.5.1 堆排序 293 9.5.2 机器调度 294 9.5.3 霍夫曼编码 297 9.6 参考及推荐读物 302 第10章 竞?303 10.1 引言 303 10.2 抽象数据类型WinnerTree 306 10.3 类WinnerTree 307 10.3.1 定义 307 10.3.2 类定义 307 ...