堆的创建

堆其实是一种完全二叉树，堆分为大堆和小堆，当满足Key[i]>Key[2i+1]以及Key[i]>Key[2i+2]时是大堆，当满足Key[i]<Key[2i+1]以及Key[i]<Key[2i+2]时是小堆。

#pragmaonce#include<vector>#include<iostream>#include<assert.h>usingnamespacestd;template<classT>classHeap{public:Heap():_a(NULL){}Heap(constT*a,size_tsize){assert(a);for(size_ti=0;i<size;i++){_a.push_back(a[i]);}for(inti=(_a.size()-2)/2;i>0;--i){_AdjustDown(i);}}voidPush(constT&x){_a.push_back(x);_AjustUp(_a.size()-1);}voidPop(){assert(_a.empty());swap(_a[0],_a[a.size()-1]);_AdjustDown();}protected:void_AdjustDown(size_tparent){size_tchild=parent*2+1;while(child>0){if(_a[child]<_a[child+1]&&child<_a.size()){++child;//如果左孩子比有孩子大的话，不做处理，反之，使得大的变成child=child+1;}if(_a[child]>_a[parent])//每次交再向下调整{swap(_a[child],_a[parent]);parent=child;child=parent*2+1;}else{break;}}}void_AjustUp(size_tchild){intparent=(child-1)/2;while(child>0)//这里必须判断孩子下标，否则很危险。如果要用父亲的判断，则应该把size_t改为int{if(_a[parent]<_a[child]){swap(_a[parent],_a[child]);child=parent;parent=(child-1)/2;}else{break;}}}protected:vector<T>_a;};voidTestHeap(){inta[]={10,11,13,12,16,18,15,17,14,19};Heap<int>Hp1(a,sizeof(a)/sizeof(a[0]));Hp1.Push(20);}intmain(){TestHeap();system("pause");return0;}

2.堆排序思想

利用大根堆小根堆堆顶元素是最大记录（最小记录），使得每次从无序中选择最大（最小记录）就变得简单了。这里采用大根堆思想，

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；

2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

//堆排序#include<iostream>#include<assert.h>usingnamespacestd;voidAjustDown(inta[],size_tn,intparent){assert(a);intchild=parent*2+1;while(child<n){if(child<n&&(a[child]<a[child+1])){++child;}if(a[child]>a[parent]){swap(a[child],a[parent]);parent=child;}else{break;}}}voidHeapSort(inta[],size_tn){assert(a);for(inti=(n-2)/2;i>0;--i){AjustDown(a,n,i);}for(inti=0;i<n;++i){swap(a[0],a[n-i-1]);AjustDown(a,n-i-1,0);}}voidTest(){inta[]={2,1,4,3,5,6,0,4,7,8,9};HeapSort(a,sizeof(a)/sizeof(a[0]));}intmain(){Test();system("pause");return0;}

算法分析：

从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。

3.堆的应用

例：100W个数中找出最大的100个

1小根堆；
2堆固定大小为100；
3堆元素个数小于100时直接加入堆；
4堆元素个数等于100时，与堆顶元素比较，比堆顶元素大的进堆，并调整堆；
5遍历结束时，堆中元素为100个最大数。

#pragmaonce#include<iostream>#include<assert.h>#include<time.h>#include<stdlib.h>usingnamespacestd;constintN=10000;constintK=100;void_AjustDown(intTopK[],intsize,intparent){assert(TopK);intchild=parent*2+1;while(child<size){if(child<size&&(TopK[child]<TopK[child+1])){++child;}if(TopK[child]>TopK[parent]){swap(TopK[child],TopK[parent]);parent=child;}else{break;}}}voidGetTop(inta[]){assert(K<N);intTopK[K];for(inti=0;i<K;++i){TopK[i]=a[i];}//建堆for(inti=(K-2)/2;i>=0;--i){_AjustDown(TopK,K,0);}for(inti=0;i<K;++i){cout<<TopK[i]<<"";}}voidTestTopK(){srand(time(0));inta[N];intTopK[K];for(inti=0;i<N;++i){a[i]=rand()%10000;}for(inti=N-K;i<N;++i){a[i]=10000+i;}GetTop(a);}intmain(){TestTopK();system("pause");return0;}