堆排序模板

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 void heapAdd(int a[],int i,int num)
 6 {
 7     a[i]=num;
 8     for(int j=i>>1;j&&i&&a[i]<a[j];i=j,j>>=1)
 9         swap(a[i],a[j]);
10 }
11 void heapDown(int a[],int i,int n)
12 {    
13     for(int j=i<<1;j<=n;i=j,j<<=1)
14     {
15         if(j+1<=n&&a[j+1]<a[j])    j++;
16         if(a[i]>a[j])    swap(a[i],a[j]);
17     }
18 }
19 void heapDel(int a[],int n)
20 {
21     swap(a[1],a[n]);
22     heapDown(a,1,n-1);
23 }
24 void makeHeap(int a[],int n)
25 {
26     for(int i=n/2;i;--i)
27         heapDown(a,i,n);
28 }
29 void heapSort(int a[],int n)
30 {
31     for(int i=n;i>1;--i)
32     {
33         swap(a[i],a[1]);
34         heapDown(a,1,i-1);
35     }
36 }
37 int main()
38 {
39     
40     return 0;
41 }

注意：使用小根堆排序后是递减数组，要得到递增数组，可以使用大根堆。

在堆排序好后再添加元素，需要重新建堆并且排序。

　　由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。

参考文章：http://blog.csdn.net/morewindows/article/details/6709644/