1、堆排序

1.1 堆排序简介

　　堆数据结构是一种数组对象，它可以被视为一棵完全二叉树，树中每个节点与数组A中存放该结点值的那个元素对应。树根为A[1]，给定了某个结点的下标i，其父节点PARENT(i),左儿子节点LEFT(i)和右儿子结点RIGHT(i）的下标可以简单的计算出来：PARENT(i）：不大于i/2的最大整数，LEFT(i):2i;RIGHT（i）：2i+1；

　　堆排序主要分成三个重要步骤：

　　（1）利用MAX-HEAPIFY来保持堆的性质：输入为数组A和下标i。当其被调用时，我们假定以LEFT（i）和RIGHT(i)为根的两棵二叉树都是最大堆，但这时A[i]可能小于其子女，这就违反了最大堆性质。MAX-HEAPIFY让A[i]在最大堆中“下降”，使以i为根的子树成为最大堆。

　　（2）BUILD-MAX-HEAP(A)建堆：自底向上的用MAX-HEAPIFY来将一个数组A[1...n]变成一个最大堆。子数组A[n/2+1...n]中的元素都是树中的叶子，因此每个都可以看做只含一个元素的堆。建堆过程对树中的每一个其他结点都调用一次MAX-HEAPIFY。

　　（3）HEAPSORT(A):利用(2)已经将数组A造成一个最大堆。因为数组中最大元素在根A[1],则可以通过把它与A[n]互换来达到最终正确的位置。现在，如果从堆中去掉结点n（通过减小A的大小），可以很容易的将A[1...n-1]建成最大堆。原来的根的子女仍是最大堆，而新的根元素可能违背了最大堆性质，这时调用MAX-HEAPIFY(A,1)就可以保持这一性质，在A[1...(n-1)]中构造出最大堆。

1.2、堆排序具体实现代码：

1 #include
      
        2 void max_heapify(int *p,int i,int n)//保持堆的性质 3 { 4     int l,r,largest,temp; 5     l=2*i; 6     r=2*i+1; 7     if((l<=n) && (*(p+l) > *(p+i))) 8         largest=l; 9     else largest=i;10     if((r<=n) && (*(p+r) > *(p+largest)))11         largest =r;12     if(largest!=i)13     {14         temp=*(p+i);15         *(p+i)=*(p+largest);16         *(p+largest)=temp;17         max_heapify(p,largest,n);18     }19 }20 void build_max_heap(int *p,int n)//建立大顶堆21 {22     int i;23     for(i=n/2;i>0;i--)24         max_heapify(p,i,n);25 }26 27 void heapsort(int *p,int n)//堆排序28 {29     int i,temp;30     build_max_heap(p,n);31     for(i=n;i>=1;i--)32     {33         temp=*(p+1);34         *(p+1)=*(p+i);35         *(p+i)=temp;36         printf("%d  ",temp);37         n--;38         max_heapify(p,1,n);39     }40 }41 int main()42 {43     int n=10;44     int a[11]={
     0,16,14,10,8,7,9,3,2,4,1};45     printf("排序结果为：\n");46     heapsort(a,n);47     return 0;48 }
      

　　堆排序算法的时间复杂度为O(nlgn);;

 

2 利用堆建立最小优先级队列

　　优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key，一个最小优先级队列支持一下操作

（1）heap_insert(S，x):把元素x插入到集合S。

（2）heap_minimun(S)：返回S中具有最大关键字的元素。

（3）heap_extract_min(S)：去掉并返回S中的具有最小关键字的元素。

（4）heap_decrease_key(S,x,k)将元素x的关键字减小到k，这里k不能大于x的原来的关键字值。

　　具体实现代码如下：

1 /*----------------------------------------------  2  *name:用最小堆实现最小优先级队列  3  *data:2012-7-3  4  *author:lp  5  *---------------------------------------------*/  6 #include
      
         7 #include
       
          8 #define maxsize 20//最大节点数  9 int realsize=10;//实际初始时节点数 10 int parent(int i)//父节点 11 { 12     return(i/2); 13 } 14 int left(int i)//左子节点 15 { 16     return(2*i); 17 } 18 int right(int i)//右子节点 19 { 20     return(2*i+1); 21 } 22 void min_heapify(int p[],int i)//保持堆的性质 23  { 24      int l,r,little,temp; 25      l=2*i; 26      r=2*i+1; 27      if(l<=realsize && p[l]
        
         0;i--) 44          min_heapify(p,i); 45 } 46 int heap_minimum(int p[])//返回堆中最大值 47 { 48      return(p[1]); 49 } 50 int heap_extract_min(int p[])//去掉并返回堆中的具有最大关键字的元素 51 { 52      int min; 53      if(realsize<1) 54      { 55          printf("堆下溢出\n"); 56          return(-1); 57      } 58      min=p[1]; 59      p[1]=p[realsize-1]; 60      realsize--; 61      min_heapify(p,1); 62      return(min); 63 } 64 int heap_decrease_key(int p[],int i,int key)//将元素i的关键字的值增加到key，这里key不能小于原来的值 65 { 66     int temp; 67      if(key>p[i]) 68      { 69          printf("key的值太大\n"); 70          return(-1); 71      } 72      p[i]=key; 73  74      while(i>1 && p[parent(i)]>p[i]) 75      { 76          temp=p[i]; 77          p[i]=p[parent(i)]; 78          p[parent(i)]=temp; 79          i=parent(i); 80      } 81      return(0);          82  } 83 void heap_insert(int p[],int key)//将关键字值为key的值插入到堆中 84 { 85      realsize++; 86      p[realsize]=INT_MAX; 87      heap_decrease_key(p,realsize,key); 88 } 89 void heap_print(int p[])//打印堆 90 { 91     int i; 92     for(i=1;i
        
       
      

3 参考资料：

（1）算法导论

（2）数据结构