(1)从1000个数据中找到k个最大数据

首先看到这个题时，可能会想到先将这1000个数据进行降序排序，即取出的前k个元素最大。时间复杂度为O（N^2）,使得程序效率低。

如何解决这个问题呢？我们的堆就派上用场喽！

解题思路：

可先创建一个数组topK[k],将100w中的前k个数据放入数组topK中，将topK中的数据建小堆，则可保证堆的第一个元素是最小的，将第k个元素与堆中第一个元素比较，若大于，则交换。对堆进行重新建小堆，取第k+1个元素与堆中第一个元素比较，以此类推，直至100w-k个元素比较完。则此时堆中的元素就是k个最大数据。

代码实现：

constintN=1000;constintK=100;voidAdjustDown(inttopK[],intparent)//建小堆{intchild=2*parent+1;while(child<K){if(child+1<K&&topK[child+1]<topK[child]){++child;}if(topK[child]<topK[parent]){swap(topK[child],topK[parent]);parent=child;child=2*parent+1;}else{break;}}}voidGetTopK(inta[],inttopK[]){assert(a);inti=0;for(i=0;i<K;++i)//将a的前K个元素放入数组中{topK[i]=a[i];}for(i=(K-2)/2;i>=0;--i)//对前K个元素建小堆{AdjustDown(topK,i);}for(i=K;i<N;++i){if(a[i]>topK[0])//将K个元素之后的每个元素和堆的第一个元素(最小元素)比较{swap(a[i],topK[0]);//若比第一个元素大，则交换AdjustDown(topK,0);//对新堆重新建小堆}}}

测试代码：

voidTest2(){inttopK[K];inta[N];srand(time(0));//随机数种子for(inti=0;i<N;++i){a[i]=rand();//随机数}GetTopK(a,topK);for(inti=0;i<K;i++){cout<<topK[i]<<"";}}

测试结果：

时间复杂度为 k*lgk+N*lgk

当N庞大时，k可忽略，则时间复杂度为O（N），大大提高了效率。


（2）堆排序

既然是排序，那就有两种可能升序or降序。使得堆是建大堆方便还是建小堆方便。

<1>若为升序，则需要建大堆。

堆的第一个元素为最大，将最大元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。

<2>若为降序，则需要建小堆。

堆的第一个元素为最小，将最小元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。

代码实现（以升序为例）：

voidAdjustDown(inta[],intparent,intsize)//建大堆{assert(a);intchild=2*parent+1;while(child<size){if(child+1<size&&a[child+1]>a[child]){++child;}if(a[child]>a[parent]){swap(a[child],a[parent]);parent=child;child=2*parent+1;}else{break;}}}voidHeapSort(inta[],intsize){assert(a);//建堆for(inti=(size-2)/2;i>=0;--i){AdjustDown(a,i,size);//建大堆}//选择最大的放到末尾，从剩下数据向下调整for(inti=0;i<size;i++){swap(a[0],a[size-1-i]);AdjustDown(a,0,size-1-i);}}//测试代码voidTestHeapSort(){inta[]={10,16,18,12,11,13,15,17,14,19};intsize=sizeof(a)/sizeof(a[0]);HeapSort(a,size);}

测试结果：