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

注：堆分为最大堆和最小堆两种，下面我们讨论的堆都是指的最大堆，最小堆的性质与其是类似的。

堆数据结构是一种数组对象，可以被视为一棵完全二叉树(这棵二叉树除最后一层外，其余每层都是填满的)；我们用一个数组来存储一个堆，表示堆的数组有两个属性：length[A]表示的是数组中的元素个数，headsize[A]表示堆中元素个数(也就是说数组中的元素不一定都是堆中的元素)。

下面不加证明的给出一些堆的性质： 对于任何一个节点,其父节点为i/2(i>1)；左儿子:2*i,右儿子：2*i+1; 对于最大堆每个节点满足：A[parent[i]]>=A[i] 含n个元素堆的高度为lgn 含n个元素堆的叶子节点的编号为:n/2+1,n/2+2,……,n。

一.堆的调整函数—保持堆的性质

考虑这样一种情况，如果对于节点i，其左右子树都是一个合法的大根堆，但是节点i不满足堆的性质，那么我们可以通过调整使得以i为根节点的树满足堆的性质。那么具体的调整过程是怎样的呢？我们令largest表示A[i],A[i*2],A[2*i+1]中最大的那个，如果largest不是i那么我们就交换A[i]和A[largest]并且递归的进入到以largest为根节点的子树中继续进行调整。具体的代码实现如下：

void MaxHeadfly(int *a,int i,int HeadSize){  ///堆调整函数：调整以i为根的子树,使得其符合大根堆的特性(在其左右子树都是合法的大根堆的情况下)  ///最大堆调整函数是堆排序中最重要的函数，是后面几个函数的重要组成部分； ///其主要思想是：先是调整根节点然后递归的调整受影响的左(右)子树，直到叶子节点        int l=2*i,r=2*i+1; ///取出节点i的左右儿子节点的编号        int largest;  ///记录最大值的节点编号        if(a[i]
   
    <=HeadSize)            largest=l;        else            largest=i;       if(a[largest]
    
     <=HeadSize)            largest=r;        if(largest!=i)        {
  ///递归调整受影响的子树                swp(a[i],a[largest]);                MaxHeadfly(a,largest,HeadSize);        }}
    
   

二.堆的建立

堆的建立其实就是一个不断调用调整函数的过程。我们知道堆的叶子节点可以看成只含有一个元素合法的大根堆，这样如果我们从第一个非叶子节点开始依次调用调整函数，就可以保证被调整的节点的左右子树都是合法的大根堆，进而可以保证调整得到的树也是合法的大根堆。具体的代码实现如下：

void BuildMaxHead(int *a,int n){ ///最大堆建立函数：通过对数组元素有序的进行调整，使得数组成为一个大根堆  ///由完全二叉树的性质：含n个元素的堆，其叶子节点编号为n/2+1,n/2+2。。。n;  ///对于叶子节点可以看成合法的单个元素的大根堆，由MaxHeadfly函数的性质可以知道  ///如果节点i不满足大根堆的性质，但是其左右子树都是合法的大根堆，那么调用MaxHeadfly  ///调整后以i为根节点可以构成一个合法的大根堆，而一个节点的左右儿子节点编号都是大于其的  ///所以我们可以从编号n/2--1的节点依次调用堆的调整函数，然后就可以得到一个大根堆了。  for(int i=n/2;i>=1;i--)          MaxHeadfly(a,i,n);}

三.堆排序

顾名思义堆排序就是利用堆的性质对数组进行排序，对于一个堆来说我们能利用的性质就是其根节点中的元素是最大的，这次每次我们都可以将A[1]与A[HeadSize]进行交换，交换以后HeadSize的值减1,并且调用MaxHeadfly(a,1,HeadSize)对堆进行调整，使得A[1]又变成剩下元素中最大的，然后继续这个过程。最后得到一个有序的数组。堆排序的时间复杂度是nlgn；具体的代码实现如下：

void HeadSort(int *a,int n){
  ///堆排序函数：实现对数组中的n个元素进行从小到大的排序，时间复杂度nlgn  ///我们知道如果一个数组构成大根堆后，那么其根节点a[1]必定是其中最大的元素  ///此时如果我们将a[1]与a[n]互换，那么a[n]就是最大的元素了；  ///但是a[1--n-1]构成的堆可能不再满足最大堆的性质，我们再调用MaxHeadfly(a,1,n-1)调整成最大堆  ///然后a[1]就成了a[1--n-1]中最大的元素了，然后我们交换a[1]和a[n-1]，那么a[n-1]和a[n]就是有序的了。  ///继续这个过程直到堆的规模减少到2，然后进行最后一次调整交换，a数组就有小到大排列了。  ///时间复杂度：建立大根堆时间O(n),每次调整时间O(lgn)共调整n-1次，所以总的复杂度nlgn        BuildMaxHead(a,n);  ///建立一个大根堆        int HeadSize = n;        for(int i=n;i>=2;i--) ///堆的规模不断减少        {               swp(a[1],a[i]);               HeadSize--;   ///交换以后就要减少堆的大小               MaxHeadfly(a,1,HeadSize);   ///根节点改变了,重新调整成大根堆        }}

下面附上一份完整的堆排序的代码：

#include
   
    #include
    
     #include
     
      using namespace std;int swp(int &a,int &b){       int t=a;        a=b;        b=t;}void MaxHeadfly(int *a,int i,int HeadSize){          int l=2*i,r=2*i+1; ///取出节点i的左右儿子节点的编号        int largest;  ///记录最大值的节点编号        if(a[i]
      
       <=HeadSize)            largest=l;        else            largest=i;       if(a[largest]
       
        <=HeadSize)            largest=r;        if(largest!=i)        {
  ///递归调整受影响的子树                swp(a[i],a[largest]);                MaxHeadfly(a,largest,HeadSize);        }}void BuildMaxHead(int *a,int n){   for(int i=n/2;i>=1;i--)          MaxHeadfly(a,i,n);}void HeadSort(int *a,int n){        BuildMaxHead(a,n);  ///建立一个大根堆        int HeadSize = n;        for(int i=n;i>=2;i--) ///堆的规模不断减少        {               swp(a[1],a[i]);               HeadSize--;   ///交换以后就要减少堆的大小               MaxHeadfly(a,1,HeadSize);   ///根节点改变了,重新调整成大根堆        }}int main(){      int n=5,a[10];      cout<<"请输入"<
        
         <<"个数："<
         
          >a[i]; HeadSort(a,n); cout<<"排序以后的数组："<
         
        
       
      
     
    
   

四.优先队列

对于一般的队列来说，满足先进先出的性质(队尾入队，对首出队)，但对于优先队列来说，每次都是最大的/最小的元素出队。堆可以实现优先队列的基本操作，利用的也是堆的性质。优先队列一些具体的函数操作及其原理见下面的代码。

#include
   
    #include
    
     #include
     
      using namespace std;#define INF 0x3f3f3f3f///一般的队列满足先进先出的性质，而优选队列不同，其///总是最大的/最小的先出队。借助于堆的性质，我们可以///在lgn的时间内实现优选队列的任何操作void swp(int &a,int &b){      int t=a;      a=b;      b=t;}void MaxHeadfly(int *a,int i,int HeadSize)///堆调整函数{        int largest;        int l=i*2,r=2*i+1;        if(a[i]
      
       <=HeadSize)             largest=l;        else             largest=i;        if(a[largest]
       
        =1;i--)               MaxHeadfly(a,i,n);}///以下为优先队列的操作int MaxNum(int *a) ///取出最大的元素{      return a[1];   ///直接返回}void IncreaseKey(int *a,int x,int k){   ///将堆中编号为x的元素的值提升到k,k不能小于原来的值。     ///这种提升只可能会导致父节点不满足最大堆的性质，所以直接向上递归的检查     a[x]=k;     while(x>1&&a[x/2]
        
         >a[i]; int HeadSize=n; BuildMaxHead(a,n); ///取出队列中 最大的那个元素 cout<<"最大的元素是: "<
         
          <
         
        
       
      
     
    
   

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