忆卉网上有关“为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？”话题很是火热，小编也是针对为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
建堆的时候你看看是不是多次调用了调堆的函数呢，那肯定就不只是logN了，如果从底部最后的父节点开始建堆，那么我们可以大概算一下：
假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 ?将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法（ Heap Sort )
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
(1)?序列?{29,?70,?54,?32,?64,?78}?有6个数据,先建立"完全二叉树",
[1]=29,[2]=70,[3]=54,[4]=32,[5]=64,[6]=78
29?[1] /\/\ 7054[2][3]/\//?\?/?
3264?78?[4][5]?[6]完全二叉树对应的顺序号
(2)?"完全二叉树"有6个结点,也就是N=6,要建立"初始堆",就要从第N/2号结点到
第1号结点进行调整,也就是按顺序,调整第3号结点,第2号结点,第1号结点,
这3个结点都有分支.
第3号结点,[3]=54,它比左分支78小,所以不用互换,二叉树保持不变,
此时,序列是?29?70?54?32?64?78
29 /\? 7054?/\/?
3264?78?(3)?第2号结点,[2]=70,它比左分支32大,比右分支64大,而左分支32较小,互换32和70,
此时,序列是?29?32?54?70?64?78
29 /\? 3254?/\/?
7064?78?(4)?第1号结点,[1]=29,它比左分支32小,比右分支54小,所以,不用互换,
此时,序列是?29?32?54?70?64?78
29 /\? 3254?/\/?
7064?78?按照"最小堆"的规则,依次完成前3个结点的调整,得到"初始堆":
29?32?54?70?64?78
接下来,就是正式的排序过程,因为使用最小堆的堆排序方法,
所以,最后排序的结果是从大到小.
(5)?根节点29与最后一个结点78互换,78成为根结点,然后,78与32,64依次互换,
这一次的调整,得到最小值29.
此时,序列是?32?64?54?70?78?29
78?32?32 /\?/\/\ 32547854?6454/\?/\?/\?
7064?297064?297078?29?(6)?根结点32与最后一个结点78互换,78成为根结点,然后,78与54互换,
这一次的调整,得到最小值32.
此时,序列是?54?64?78?70?32?29
78?54 /\?/\64546478
/?/? 7032?297032?29?(7)?根结点54与最后一个结点70互换,70成为根结点,70与64互换,
这一次的调整,得到最小值54.
此时,序列是?64?70?78?54?32?29?
7064
/\/\6478?7078
5432?29?5432?29?(8)?根结点64与最后一个结点78互换,78成为根结点,78与70互换,
这一次的调整,得到最小值64.
此时,序列是?70?78?64?54?32?29
7870
/?/7064?7864
5432?29?5432?29?(9)?根结点70与最后一个结点78互换,最后得到一个完全有序的序列(从大到小):
78?70?64?54?32?29?
图示:
787064
5432?29?//C语言测试程序
//使用最小堆的堆排序方法
#include?<stdio.h>
char?fileName[]="d:\\heapSort.txt";
int?printIndex;
int?writeindex;
void?printData(int?*a,int?n)?//屏幕打印数据
{
int?i;
printf("(%d)?",printIndex);
for(i=0;i<n;i++)
{
printf("%d?",a[i]);
}
printf("\n");
printIndex++;
}
void?writeFile(int?*a,int?n)?//排序过程写入文件
{
FILE?*fp;
int?i;
fp=fopen(fileName,"a");?//"a"以附加的方式打开只写文件
if(fp?==?NULL)
{
printf("\n打开文件?%s?时出错.\n",fileName);
return;
}
fprintf(fp,"(%d)?",writeindex);
for(i=0;i<n;i++)
{
fprintf(fp,"%d?",a[i]);
}
fprintf(fp,"\n");
fclose(fp);?//关闭文件
writeindex++;
}
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void?HeapAdjust(int?array[],int?i,int?nLength)
{
int?nChild;
int?nTemp;
for(;2*i+1<nLength;i=nChild)
{
//子结点的位置=2*（父结点位置）+1
nChild=2*i+1;
//得到子结点中较小的结点
if(nChild?<?nLength-1?&&?array[nChild+1]?<?array[nChild])
{
++nChild;
}
//如果较小的子结点小于父结点那么把较小的子结点往上移动，替换它的父结点
if(array[i]?>?array[nChild])
{
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}
else?break;?//否则退出循环
}
}
//堆排序算法
void?HeapSort(int?array[],int?length)
{
int?i;
//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点.
for(i=length/2-1;i>=0;--i)
{
HeapAdjust(array,i,length);
printData(array,length);
writeFile(array,length);
}
printIndex=1;
writeindex=1;
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i)
{
//把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i]=array[0]^array[i];
array[0]=array[0]^array[i];
array[i]=array[0]^array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
printData(array,length);
writeFile(array,length);
}
}
int?main()
{
int?num[]={29,70,54,32,64,78};
int?i;
int?len;
len=sizeof(num)/sizeof(int);
printIndex=0;
writeindex=0;
printData(num,len);
writeFile(num,len);
HeapSort(num,len);
printf("最后结果:\n");
for(i=0;i<len;i++)
{
printf("%d?",num[i]);
}
printf("\n排序的过程保存在文件?%s\n",fileName);
return?0;
}
关于“为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
评论列表（3条）
我是中宝号的签约作者“忆卉”
本文概览：网上有关“为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？”话题很是火热，小编也是针对为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？寻...
文章不错《为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN？》内容很有帮助