深入理解堆排序及其分析
记得在学习数据结构的时候一味的想用代码实现算法,重视的是写出来的代码有一个正确的输入,然后有一个正确的输出,那么就很满足了。从网上看了许多的代码,看了之后貌似懂了,自己写完之后也正确了,但是不久之后就忘了,因为大脑在回忆的时候,只依稀记得代码中的部分,那么的模糊,根本不能再次写出正确的代码,也许在第一次写的时候是因为参考了别人的代码,看过之后大脑可以进行短暂的高清晰记忆,于是欺骗了我,以为自己写出来的,满足了成就感。可是代码是计算机识别的,而我们更喜欢文字,图像。所以我们在学习算法的时候要注重算法的原理以及算法的分析,用文字,图像表达出来,然后当需要用的时候再将文字转换为代码。记忆分为三个步骤:编码,存储和检索,就以学习为例,先理解知识,再归纳知识,最后巩固知识,为了以后的应用而方便检索知识。
既然是堆排序,自然需要先建立一个堆,而建堆的核心内容是调整堆,使二叉树满足堆的定义(每个节点的值都不大于其父节点的值)。调堆的过程应该从最后一个非叶子节点开始,假设有数组A={1,3,4,5,7,2,6,8,0}。那么调堆的过程如下图,数组下标从0开始,A[3]=5开始。分别与左孩子和右孩子比较大小,如果A[3]最大,则不用调整,否则和孩子中的值最大的一个交换位置,在图1中是A[7]>A[3]>A[8],所以A[3]与A[7]对换,从图1.1转到图1.2。
所以建堆的过程就是
for(i=headLen/2;i>=0;i++)
doAdjustHeap(A,heapLen,i)
建堆完成之后,堆如图1.7是个大根堆。将A[0]=8与A[heapLen-1]交换,然后heapLen减一,如图2.1,然后AdjustHeap(A,heapLen-1,0),如图2.2。如此交换堆的第一个元
素和堆的最后一个元素,然后堆的大小heapLen减一,对堆的大小为heapLen的堆进行调堆,如此循环,直到heapLen==1时停止,最后得出结果如图3。
/*
输入:数组A,堆的长度hLen,以及需要调整的节点i
功能:调堆
*/
voidAdjustHeap(intA[],inthLen,inti)
{
intleft=LeftChild(i); //节点i的左孩子
intright=RightChild(i);//节点i的右孩子节点
intlargest=i;
inttemp;
while(left<hLen||right<hLen)
{
if(left<hLen&&A[largest]<A[left])
{
largest=left;
}
if(right<hLen&&A[largest]<A[right])
{
largest=right;
}
if(i!=largest) //如果最大值不是父节点
{
temp=A[largest];//交换父节点和和拥有最大值的子节点交换
A[largest]=A[i];
A[i]=temp;
i=largest; //新的父节点,以备迭代调堆
left=LeftChild(i); //新的子节点
right=RightChild(i);
}
else
{
break;
}
}
}
/*
输入:数组A,堆的大小hLen
功能:建堆
*/
voidBuildHeap(intA[],inthLen)
{
inti;
intbegin=hLen/2-1; //最后一个非叶子节点
for(i=begin;i>=0;i--)
{
AdjustHeap(A,hLen,i);
}
}
/*
输入:数组A,待排序数组的大小aLen
功能:堆排序
*/
voidHeapSort(intA[],intaLen)
{
inthLen=aLen;
inttemp;
BuildHeap(A,hLen); //建堆
while(hLen>1)
{
temp=A[hLen-1]; //交换堆的第一个元素和堆的最后一个元素
A[hLen-1]=A[0];
A[0]=temp;
hLen--; //堆的大小减一
AdjustHeap(A,hLen,0); //调堆
}
}
性能分析
•调堆:上面已经分析了,调堆的运行时间为O(h)。
•建堆:每一层最多的节点个数为n1=ceil(n/(2^(h+1))),
因此,建堆的运行时间是O(n)。
•循环调堆(代码67-74),因为需要调堆的是堆顶元素,所以运行时间是O(h)=O(floor(logn))。所以循环调堆的运行时间为O(nlogn)。
总运行时间T(n)=O(nlogn)+O(n)=O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间,因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n),而在总体时间中占重要比例的是循环调堆的过程,即O(nlogn)+O(1)=O(nlogn)+O(n)=O(nlogn)。因此最好或者最坏情况下,堆排序的运行时间都是O(nlogn)。而且堆排序还是原地算法(in-placealgorithm)。
相关文章
- 深入理解Linux问题分析与性能优化(超详细~)
- 8-1. 「webpack源码分析」一个具体案例再次深入看buildChunkGraph的运行过程
- 【Groovy】MOP 元对象协议与元编程 ( Groovy 类内部和外部分别获取 metaClass | 分析获取 metaClass 操作的字节码 | HandleMetaClass 注入方法 )
- Servlet容器Tomcat中web.xml中url-pattern的配置详解[附带源码分析]编程语言
- 深入理解Oracle数据库性能分析(oracle性能分析)
- 深入理解Linux内部结构(linux结构分析)
- 深入理解Java中的逃逸分析详解编程语言
- 报告Linux AWR报告——深入探索服务性能分析(linuxawr)
- MySQL源码分析:深入理解数据库引擎(mysqlsrc)
- Linux网卡驱动:深入剖析(linux网卡驱动分析)
- 分析Oracle数据库优化查询语句:深入理解执行计划(oracle看执行计划)
- 深入剖析Linux抓包分析技巧:实现网络问题精准定位(linux抓包分析)
- MySQL源码分析:从入门到深入(mysql源码分析)
- 深入理解Oracle的操作日志分析(oracle查看操作日志)
- 深入理解MySQL索引:分析与优化(mysql索引分析和优化)
- 深入了解Linux程序性能分析技术(linux程序性能分析)
- Linux网络源码分析:深入理解操作系统核心技术(linux网络源码)
- 深入理解Linux系统内存使用分析(linux 内存使用分析)
- MySQL中ref字段不匹配问题分析(mysql中ref不对)
- 分析Redis源码深入了解缓存存储引擎(解剖redis源码书籍)
- 深入了解MySQL工作原理分析(11 mysql工作原理)
- 深入理解Redis默认存储方式分析(redis 默认存储方式)
- 深入探索Redis集群的源码分析(redis集群分析源码)
- 深入理解goto语句的替代实现方式分析
- 深入oracle特定信息排序的分析
- 深入XPath的详解以及Java示例代码分析
- 深入mysql"ONDUPLICATEKEYUPDATE"语法的分析