堆【数据结构C语言版】【 详解】

一、思考

设计一种数据结构，来存放整数，要求三个接口：
1）获取序列中的最值（最大或最小）
2）添加元素
3）删除最值（最大或最小）

分析：

1）如果使用无序的线性表来实现，则需要发现获取最值、删除最值都需要遍历全部数据，复杂度为O(n)
2）如果使用有序的线性表，则查找并删除最值是虽是O(1)级别，但插入一个元素要重新进行排序，最好情况也是O(n)
3）如果平衡二叉查找树实现，虽然查找、插入、删除复杂度是O(log<sub>2</sub>n)级别，但其实现程度复杂，功能多，
   对于仅实现三个接口来说是”大炮打蚊子“，得不尝失。而使用”堆“能很好实现三种接口，且时间复杂度较低，
   获取最大值O(1)，添加、删除都为O(log<sub>2</sub>n)

（注：这里的堆不是内存模型里的”堆空间“，勿要混淆）

二、堆概念与性质

堆(Heap)是一种数据结构，物理存储采用顺序表，其元素必须满足的性质是：
{ k i ≤ k 2 i + 1 k i ≤ k 2 i 或 { k i ≥ k 2 i + 1 k i ≥ k 2 i \lbrace^{k_i \leq k_{2i}}_{k_i \leq k_{2i+1}} 或 \lbrace^{k_i \geq k_{2i}}_{k_i \geq k_{2i+1}} {ki​≤k2i+1​ki​≤k2i​​或{ki​≥k2i+1​ki​≥k2i​​
我们称前者为小顶堆(或小根堆），后者为大顶堆(或大根堆）。观察发现，这和完全二叉树的性质5很一样，因此可以逻辑上理解堆为一棵完全二叉树。
例如：序列（5，7，6，9，8，10）满足小根堆的性质
这棵完全二叉树的根元素又叫堆顶元素，也是序列中的最小值，因此，每次查找最小值只需要获取堆顶元素即可，添加一个元素后，需要对堆重新进行调整每个元素满足堆性质，成为一个新堆；删除元素就是堆顶元素出堆，然后重新调整元素位置，直到全部元素满足堆性质，成为一个新堆。

三、堆的构建、删除、添加

1. 构建

（以小顶堆为例）
如何使一个序列变成满足堆性质的序列，并且具有添加、删除、获取最值三大接口？需要思考两个问题
1）如何由该混乱的序列构建一个堆？
2）往堆里添加、删除(删除堆顶）元素后，如何调整剩余元素成为一个新的堆？

已知一个混乱序列（10，8，6，9，7，5），和一个空堆H，然后遍历序列，每遍历一个序列往空堆添加元素，既要考虑每个元素满足堆的性质，又要思考新添加的元素位置（放在$i$的位置还是$i+1$的位置），发现这种代码逻辑很难实现。由堆的性质和完全二叉树的性质类似，把已知的混乱序列逻辑上形象的看成一个完全二叉树。那么问题就转化为如何把一个”混乱“的完全二叉树转变为一棵小根堆对于的完全二叉树

观察图发现，我们只需要从非叶子$\lfloor n/2\rfloor$结点开始，以它为根，对其根以及根的所有后代元素进行调整使其成为一棵小根堆，直到$\lfloor n/2\rfloor -1$ ~ $1$位置为根元素都调整完毕，构建堆完成。
如何调整？

（注：假设现在有一个小根堆序列，其对应的完全二叉树如上图所示）
1）堆顶元素输出或出堆，让表尾元素（11）覆盖（5）并删除表尾元素
2）根(11)和其左右孩子（7，6）中最小的比较，发现6比11小，则6和11交换位置，这时以11为根的子树继续调整，10比11小，则互换位置…直到叶子结点（若中途发现根比孩子中最小的还小，则操作结束，该棵子树已经调整好了）
知道了如何调整，那么堆的构建就是从非叶子$\lfloor n/2\rfloor$结点为根的树进行调整，直到$\lfloor n/2\rfloor -1$ ~ $1$位置为根的每棵树都调整一遍，即堆构建完成

typedef int HeapType;
//构建堆，传入一个无序序列和序列长度，时间复杂度为O(n)
HeadType* CreateHeap(HeapType *H,int length){//由无序序列 H构建堆,该序列从索引0开始 
	int s;
	for(s=length/2-1;s>=0;s--){//建立堆
		AdjustHeap(H,s,length);//调整函数
	}
	return H;
}

//堆排序 ---O(nlogn)
void HeapSort(HeapType *H){
	int s;
	int top;
	//堆顶元素出堆，表尾元素覆盖堆顶（删除表尾元素，即空出表尾单元），原堆顶元素放在表尾
	for(s=length;s>1;s--){//进行length-1次出堆，直到堆中只剩一个元素（该元素的索引：0）
		top=H[0];
		H[0]=H[s-1];
		AdjustHeap(H,0,s-1);
		H[s-1]=top;
	} 
}

2. 删除

堆中的删除操作，就是删除堆顶元素，其步骤和上文的如何调整一致，其调整函数如下

void AdjustHeap(HeapType*H,int s,int len){	//s=len/2-1
	//保存以索引s位置元素为根，此时s位置的结点并不满足最小堆的性质，其
	//他所有结点(s到len-1)位置的结点满足小顶堆的性质 
	int rc=H[s];
	int i;
	for(i=2*s+1;i<len;i=2*i+1){//由完全二叉树的性质：孩子结点和双亲结点的索引关系(注：结点位置从索引0开始，因此i=2*s+1而不是i=2*s)
		if(i<len-1&&H[i]>H[i+1])i++;//索引i是s孩子中的最小元素的索引
		if(rc<=H[i]) break;//若索引s处的元素小于孩子中最小的一个，则调整结束
		H[s]=H[i];
		s=i;
	}
	H[s]=rc;
}

3. 添加

往堆中添加元素，就是先把新元素放在堆的末端，再对新元素结点执行向上的操作，即让其和双亲结点比较，若新元素结点小于双亲结点则它们互换位置，若互换后，再于其双亲比较、交换，直到整棵树的根结点（索引为0的元素），若中途遇到双亲小于新元素的，则执行向上的操作结束，添加完毕

void addElement(HeapType *H,HeapType e,int len){//注：这里假设数组长度大(不会越界)，len是元素的个数
	int newIndex=len;//新元素的索引
	int i=(newIndex+1)/2-1;//i是新元素的双亲的索引
	int eElem=e;//暂存新元素
	for(i;i>=0;i=(i-1)/2{//向上执行到根（0号结点）
		if(tElem<H[i]){
			H[newIndex]=H[i];
			newIndex=i;
		}else{
			break;	
		}
	}
	H[newIndex]=eElem;
}

四、复杂度分析

4.1 时间复杂度

创建堆，是从非叶子结点$\lfloor n/2\rfloor$位置的元素开始到根，要调整的内部结点总数有$\lfloor n/2\rfloor$，这些结点分布在多个层次，而构建堆过程中，每次循环都要调用一次调整函数AdjustHeap()，其每次执行调整函，其中需要比较的次数和其结点所在的树中的层次到叶子结点的深度有关（最坏的情况下）。
推导过程如下：
假设已知现在有目标堆是一个满堆，即其对应结点总数为n=2^h-1的完全二叉树（也是满二叉树），深度为h，根结点处于第1层。我们处于第h-1层的每个非叶子结点向下调整时最多比较一次，第h-2层的最多比较2次…，第一层的根结点则比较n-1次（注：这里没计入筛选孩子中最小值的那一次比较）。第一层结点数：2^1-1=1，第二层结点数：2^2-1…第h-1层的结点总数：2^h-2，则总的比较次数S=可能比较抽象，如下表

则总的比较次数：
$$S=(h-1)+2\ast (h-2)+2^2\ast (h-3)+...+2^{h-3}\ast 2+2^{h-2}\ast 1=2^h-h-1$$

又由于n = 2^h - 1，即 h=log₂(n+1)，则代入上式中，S=n-h，即创建堆时总比较次数S为O(n)级。往往堆排序过程中，就包含建堆(O(n))和排序两个过程，后者每输出一个堆顶元素，则执行一次对根结点的调整(比较的次数规模：O(h))，即时间复杂度为：O(log₂n）,综合为：O(nlog₂n)

4.2 空间复杂度

常数级：O(1)

五、总结

堆排序，在排序过程中使用常数个辅助单元，其建堆时间为O(n)，之后执行n-1次对当前的根向下的操作，不管给定的初始序列是有序还是无序，其用堆来排序的最好、最坏、平均时间复杂度均为：O(nlog₂n），同时它是一种不稳定的排序，虽然堆排序速度很快，和快速排序时间复杂度一个水平，但其速度却不如快速排序（和时间复杂度的常数因子有关）。快速排序虽然很快，但是最坏的情况下时间复杂度达到O(n²），空间复杂度达到O(n）
（注：一般说某排序算法时间复杂度是多少，通常指平均情况下的）