本文共 1845 字，大约阅读时间需要 6 分钟。

一、知识点

1、完全二叉树=完全二叉堆

大顶堆根节点一定是最大值 2、上滤 3、下滤 4、建立最大堆（大根堆）算法

堆（Heap）是一个可以被看成近似完全二叉树的数组。树上的每一个结点对应数组的一个元素。除了最底层外，该树是完全充满的，而且是从左到右填充。—— 来自：《算法导论》堆包括最大堆和最小堆：最大堆的每一个节点（除了根结点）的值不大于其父节点；最小堆的每一个节点（除了根结点）的值不小于其父节点。堆常见的操作：HEAPIFY 建堆：把一个乱序的数组变成堆结构的数组，时间复杂度为 O(n)O(n)。HEAPPUSH：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 O(log\ n)O(log n)。HEAPPOP：从最大堆中取出最大值或从最小堆中取出最小值，并将剩余的数组保持堆结构，时间复杂度为 O(log\ n)O(log n)。HEAPSORT：借由 HEAPFY 建堆和 HEAPPOP 堆数组进行排序，时间复杂度为 O(n\ log\ n)O(n log n)，空间复杂度为 O(1)O(1)。堆结构的一个常见应用是建立优先队列（Priority Queue）。

void BuildMaxHeap(ElemType A[],int len){
   	for(int i=len/2;i>0;i--)//从i=[n/2]~1,反复调整堆 		HeadAdjust(A,i,len);	} void HeadAdjust(ElemType A[],int k,int len)//函数HeadAdjust将元素k为根的子树进行调整 {
   	A[0]=A[k];//A[0]暂存子树的根结点 	for(i=2*k;i<=len;i*=2){
   //沿key较大的子节点向下筛选 		if(i
   
    
     =A[i]) break;//筛选结束 		else{
   			A[k]=A[i];//将A[i]调整到双亲节点上 			k=i;//修改k值，以便继续向下筛选 		}	}	A[k]=A[0];//被筛选结点的值放入最终位置 }
    
   

5、堆排序算法

void HeapSort(ElemType A[],int len){
   	BuildMaxHeap(A,len);//初始建堆 	for(i=len,i>1;i--)//n-1躺的交换和建堆过程 	{
   		Swap(A[i],A[1]);//输出堆顶元素（和堆底元素交换） 		HeadAdjust(A,1,i-1);//调整，把剩余的i-1个元素整理成堆		}	}

6、空间效率O（1）

时间复杂度O（nlog N） 不稳定 二、例题 1、堆和二叉排序树区别 以小根堆为例，堆的特点是双亲结点的关键字必然小于等于该孩子结点的关键字，而两个孩子结点的关键字没有次序规定。而二叉排序树中，每个双亲结点的关键字均大于左子树结点的关系，均小于右子树结点的关键字。 2、有n个元素已构成一个小根堆，现在要增加一个元素Kn+1，请用文字简要说明如何在log2 n的时间内将其重新调整为一个堆。 将Kn+1插入到数组的第n+1个位置（即作为一个树叶插入），然后将其与双亲比较，若它大于其双亲则停止调整，否则将Kn+1与其双亲交换，重复地将Kn+1与其新的双亲比较，算法终止于Kn+1大于等于其双亲或Kn+1本身已上升为根

3、判断一个序列是否构成小根堆

bool IsMinHeap(ElemType A[],int len){
   	if(len%2==0){
   		if(A[len/2]>A[len])			return false;		for(i=len/2-1;i>=1;i--)			if(A[i]>A[2*i]||A[i]>A[2*i+1])				return false;	}else{
   		for(i=len/2;i>=1;i--)			if(A[i]>A[2*i]||A[i]>A[2*i+1])				return false; 	}	 return true; }

4、堆的数据结构能够使得堆顶总是维持最大（对于大根堆）或最小（对于小根堆），给定一个数组，对这个数组进行建堆，则平均复杂度是多少？如果只是用堆的 push 操作，则一个大根堆依次输入 3,7,2,4,1,5,8 后，得到的堆的结构示意图是下述图表中的哪个？（）

转载地址：http://rwgwi.baihongyu.com/