数据结构——堆排序

杨伟彬
杨伟彬   发布于 2018-12-28 14:15
阅读量: 46

1. 堆排序原理

       堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。

      n个元素的序列\({ k_1,k_2,…,k_n }\)当且仅当满足下列关系时,称之为堆。

        堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

       堆排序:将无序序列建成一个堆,得到关键字最小(大)的记录;输出堆顶的最小(大)值后,将剩余的n-1个元素重又建成一个堆,则可得到n个元素的次小值;如此重复执行,直到堆中只有一个记录为止,每个记录出堆的顺序就是一个有序序列,这个过程叫堆排序。一般升序采用大顶堆,降序采用小顶堆。

2. 堆排序需解决的两个问题:

  (1)、如何由一个无序序列建成一个堆?

  (2)、在输出堆顶元素后,如何将剩余元素调整为一个新的堆? 

我们先看第二个问题:

        输出堆顶元素之后,以堆中最后一个元素替代之;然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”。

        对深度为 k 的堆,“筛选”所需进行的关键字比较的次数至多为2(k-1)。

下面我们来解决第一个问题:构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。

方法:从无序序列的第\(⌊n∕2⌋\)个元素(即无序序列对应的完全二叉树的最后一个内部结点)起,至第一个元素止,进行反复筛选。

代码如下

void HeapAdjust(HeapType &H,int s,int m)
//已知H.r[s...m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数调整
// H.r[s]的关键字,使H.r[s...m]成为一个大顶堆(对其中记录的关键字而言)
//自下而上依次创建大顶堆,如果只改变最上面的
{
	int j;
	for(j = 2 * s;j <= m; j *= 2)	//沿key较大的孩子结点向下筛选
	{
		if( j < m && LT(H.r[j].key,H.r[j+1].key))
			++j;					//j两个子节点中为key较大记录的下标
		
		if(!LT(H.r[s].key,H.r[j].key))
			break;	
//让子结点较大key值和父结点s比较,若小于父节点key,跳出循环
		H.r[0] = H.r[s];			//否则,交换key值较大子结点和父结点
		H.r[s] = H.r[j];
		H.r[j] = H.r[0];			
		
   		s = j;						//交换完成后,继续比较子结点j对应的子结点
		
	}
}

void HeapSort(HeapType &H)
	//对顺序表H进行堆排序
{
	int i;
	RedType temp;
	for(i = H.length / 2; i > 0; --i)//把H.r[1...H.length]建成大顶堆
	{
		HeapAdjust(H, i, H.length);	 
//从最后一个非终端结点开始,依次调整所有的结点,使之成为大顶堆
	}
	for(i = H.length; i > 1; --i)
	{
	//将堆顶记录和当前未经排序子序列H.r[1...i]中
		H.r[0] = H.r[1];			 
		H.r[1] = H.r[i];			 //最后一个记录相互交换
		H.r[i] = H.r[0];
		
		HeapAdjust(H, 1, i-1);	//将H.r[1...i-1]重新调整为大顶堆
	}
}

3.效率分析

(1)对深度为 k 的堆,“筛选”所需进行的关键字比较的次数至多为 2(k-1);

(2)对n个关键字,建成深度为\(h(=log_2⁡n+1)\)的堆,所需进行的关键字比较的次数至多4n;

(3)调整“堆顶”n-1次,总共进行的关键字比较的次数不超过

\(2(⌊log_2⁡(n-1) ⌋+⌊log_2⁡(n-2) ⌋⁡+⋯+⌊log_2⁡2 ⌋<2n(⌊log_2⁡n ⌋)\)

因此,堆排序的时间复杂度为\(O(n log⁡n )\),与简单选择排序\(O(n^2 )\)相比时间效率提高了很多。 

       空间复杂度:\(S(n)=O(1)\),因此,堆排序是一种速度快且省空间的排序方法。

收藏 转发 评论