基本知识：

     堆的最基本的几种操作：建堆，时间复杂度为O(n)，具体计算如下：假设有n=2^k个元素，从n/2元素开始， 以该点为根，使之成为一个堆； 然后再以n/2-1元素开始， 使之成为一个堆。。。，直到数组第1个元素，使之成为一个堆； 于是整个数组就成为一个堆了。杂度是2^(k-1) * 1 + .... + 2 * (k-1) + 1 * k                       ====>2^k       ==> n

     堆排序复杂度O(n*lgn)。另外，一个堆可以在O(lgn)时间内，支持大小为n的集合上的任意优先队列操作。

应用——优先队列：

      鉴于堆的性质，可以应于优先队列，优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key。一个优先级队列支持的操作为插入、提取、提取最大值、修改增大key值等；对于不同的key值可以运用到不用的环境，比不key为时间可以运用与FIFO的队列（大堆，小堆为栈）；

其他：

鉴于堆的每次提取最”优“性质元素，可以创建一个k大小的堆进行对k个已排序链表进行k路合并。下面直接上代码，对上面几种情况进行了总结：

1 #include 
      
          2  #include 
       
           3  #include 
        
            4    5  #define M 10   6    7  /**   8  * 注意：对于C语言数组下标从0开始，而算法的下标从1开始，解决办法有两个：   9  * 1,调整算法小标，让其适应数组下标，如下面的max_heap函数，所以这里需要取i*2+1与i*2+2的值作为i的左右子树；  10  * 2,调整C语言数组下标，适应算法下标，如下面的max_hep_e函数，这种方法比较简单，访问数组时下标只要减一就可以了；  11  * 整体比较而言，调整数组下标以适应算法比较简单，也是通用做法。  12  *  13  * 3,对于堆排序而言，交换的次数为n-2次，建堆的次数为n-1次；次数增加将出错；  14  * 4,算法要注重细节  15  **/  16   17  int heap_size=M;  18   19  /*非递归求解，调整算法下标*/  20  int* max_heap(int *a,int i)  21  {
     22      int max,tmp;  23      int N=heap_size;  24   25      while(i*2+1
         
          a[max])max=i*2+2;  30          if(max==i)  31          {
     32              break;  33          }else  34          {
     35              tmp=a[i];  36              a[i]=a[max];  37              a[max]=tmp;  38              i=i*2+1;  39   40          }  41      }  42      return a;  43  }  44  /*非递归，调整数组下标*/  45  int* max_heap_e(int *a,int i)  46  {
     47      int max,tmp;  48      int N=heap_size;  49   50      while(i*2
          
           a[max-1])max=i*2+1;  55          if(max==i)  56          {
     57              break;  58          }else  59          {
     60              tmp=a[i-1];  61              a[i-1]=a[max-1];  62              a[max-1]=tmp;  63              i=i*2;  64   65          }  66      }  67      return a;  68  }  69   70  /*递归求解*/  71  int *max_heap_recur(int *a,int i)  72  {
     73      int max=i,tmp;  74      int N=heap_size;  75   76      if(2*i+1
           
            a[i])max=2*i+1; 77 if(2*i+2
            
             a[max])max=2*i+2; 78 if(i!=max) 79 { 80 tmp=a[i]; 81 a[i]=a[max]; 82 a[max]=tmp; 83 max_heap_recur(a,max); 84 } 85 return a; 86 87 } 88 /*创建堆*/ 89 int* build_max_heap(int *a) 90 { 91 int i=0; 92 for(i=M/2;i>=0;i--)/*C语言从0开始，调整算法下标，这里需要i>=0才能访问到根节点*/ 93 // a=max_heap(a,i); 94 a=max_heap_recur(a,i); 95 return a; 96 } 97 98 99 100 int* build_max_heap_e(int *a) 101 { 102 int i=0; 103 for(i=M/2;i>=1;i--)/*不需要调整算法的下标*/ 104 a=max_heap_e(a,i); 105 // a=max_heap_recur(a,i); 106 return a; 107 } 108 109 int *heap_sort(int *a) 110 { 111 int i,tmp; 112 a=build_max_heap_e(a); 113 114 int n=heap_size; 115 116 for(i=n;i>2;i--)/*n-2次交换，n-1次建堆；多一次将出错*/ 117 { 118 tmp=a[0]; 119 a[0]=a[i-1]; 120 a[i-1]=tmp; 121 heap_size--; 122 max_heap_e(a,1); 123 } 124 return a; 125 } 126 127 128 void print(int *a) 129 { 130 int i; 131 for(i=0;i
             
              key) 163 { 164 printf("wrong input"); 165 return 0; 166 } 167 a[i-1]=key; 168 169 for(j=i/2;j>1;j=j/2) 170 { 171 if(a[i-1]>a[j-1]) 172 { 173 tmp=a[i-1]; 174 a[i-1]=a[j-1]; 175 a[j-1]=tmp; 176 }else 177 break; 178 } 179 return a; 180 } 181 182 int *max_heap_insert(int *a,int key) 183 { 184 a[heap_size++]=-65535; 185 return heap_increase_key(a,heap_size,key); 186 } 187 188 int main(void) 189 { 190 int a[20]={ 2,17,3,16,13,10,1,5,7,12}; 191 int *b=NULL; 192 int *c=NULL; 193 int *d=NULL; 194 int *e=NULL; 195 int size_tmp=heap_size; 196 197 198 print(a); 199 b=build_max_heap(a); print(b); 200 c=build_max_heap_e(a); print(c); 201 202 203 204 build_max_heap_e(a); print(a); 205 e=max_heap_insert(a,15); 206 print(e); 207 208 209 // build_max_heap(a); 210 heap_size=size_tmp; 211 d=heap_sort(e); 212 213 heap_size=size_tmp; 214 print(d); 215 216 return 0; 217 }
             
            
           
          
         
        
       
      

实验结果：