数据结构----堆(1)

1、堆及性质

堆，或者叫二叉堆，可以被视为一棵完全二叉树。树中每个节点与数组中存放该节点值的那个元素相对应。树的每一层都是填满的，除了最后一层。节点在堆中的高度定义为从本节点到叶子节点的最长简单下降路径上边的数目，而堆的高度就是树根的高度。因此，在高度为h的堆中，共有h+1层，最多有2^(h+1)-1个元素，最少有2^h个元素。而n个元素的堆的高度为log₂n最小值。

2、分类

二叉堆分为两种：最大堆和最小堆(小根堆)。最大堆(最小堆)指每个节点的值都比其两个子节点的值要大或等于(小或者等于)。

最大堆用于堆排序中，最小堆通常用于构造优先队列时用。

3、建堆子程序

首先，介绍最大堆操作的一个重要子程序Max_Heapify(A,i),输入是一个数组A和下标i，此程序将以i为根的子树成为最大堆，但前提是i为根的两个子树都已经是最大堆。其将A[i]在最大堆中下降，知道找到合适的位置满足以i为根的子树成为最大堆。

程序如下：void max_heapify(int A[],int len,int i){

   int l=2*(i+1)-1;//左孩子下标
   int r=2*(i+1);//右孩子下标
   int largest=i;//初始化时，将largest设为i，否则到达叶子时由于初始不等于i会出现死循环一直递归
   int temp=0;
   if(l<len&&A[l]>A[i]){//1
       largest=l;
   }
   if(r<len&&A[r]>A[largest]){//2,这两处小于号是求最小堆，大于号是最大堆
       largest=r;
   }

   if(i!=largest){
      temp=A[i];
	  A[i]=A[largest];
	  A[largest]=temp;
	  max_heapify(A,len,largest);
   }
}

程序是个递归的过程，首先找到节点i和两个子节点这三个节点中值最大的下标存入largest，如果最大的就是A[i],以i为根的子树已经是最大堆，程序结束。否则，将A[largest]和A[i]互换，交换后，下标为largest的节点的值是A[i],此时再往下降，调用此时的以largest为根节点的递归程序。

Max_Heapify用于一个高度为h的节点所需的运行时间为O(h).

4、建堆

自底向上的用Max_Heapify来将数组A[0,...,n-1]变成最大堆，由于A[n/2+1,....,n-1]都是叶子节点，没有子节点，因此不需要执行。所以只需从n/2自底向上到0，调用Max_Heapify。

为什么自底向上？因为Max_Heapify的前提是左右两个子树必须是最大堆，因此，自底向上，保证这个前提条件。下面是建堆程序：

 

int main(){
	int A[10]={16,4,10,14,7,9,3,2,8,1};
        int len=10;
	for(int i=len/2;i>=0;i--){//建最大堆或者最小堆
	   max_heapify(A,len,i);//min_heapify(A,len,i)
	}

	return 0;
}

 

 

分析建堆算法，Max_Heapify运行时间O(log₂n)，共有O(n)次调用，故运行时间O(nlog₂n)。更精确的，根据二叉树的性质，在任意高度h上，至多有n/2^(h+1)(取最大值)个节点。一个n元素堆的高度为log₂n，因此，可算得运行时间为

O(n),即在线性时间里，可以完成最大堆(最小堆)的建立。