海量数据中，寻找最小的k个数。

维护k个元素的最大堆，即用容量为k的最大堆存储最小的k个数，k1设为大顶堆中最大元素。遍历一次数列，n，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆，否则不更新堆。

 1 // 海量数据中，寻找最小的k个数（堆）.cpp : 定义控制台应用程序的入口点。
 2 
 3 #include "stdafx.h"
 4 #include <string.h>
 5 #define MAX 1000
 6 
 7 void swap(int &a,int &b)
 8 {
 9     int c;
10     c=a;
11     a=b;
12     b=c;
13 }
14 
15 void max_heapity(int heap[],int i,int len)//保持最大堆性质
16 {
17     int left=2*i, right=2*i+1,largest=-1;
18     if((left<=len)&&(heap[left]>heap[i]))
19         largest=left;
20     else 
21         largest=i;
22     if((right<=len)&&(heap[right]>heap[largest]))
23         largest=right;
24     if(largest!=i)
25         {
26             swap(heap[largest],heap[i]);
27             max_heapity(heap,largest,len);
28         }
29 }
30 
31 void build_maxheap(int heap[],int len) //建立最大堆
32 {
33     int index=len/2;
34     for(int i=index;i>=1;i--)
35          max_heapity(heap,i,len);
36 }
37 
38 void main()
39 {
40     int k=5,heap[]={0,3,12,6,7,15,13,24,1,4,9,10,16,20,63,45,37,86};//这里只列了少量数据进行验证，实际中应该从文件中读取数据
41     //第一个元素不计入，因这里有关堆的算法都是从下标为1开始的
42     int len=sizeof(heap)/sizeof(heap[0]);
43     build_maxheap(heap,k);//建立k个元素的最大堆
44     for(int i=1;i<len;i++)
45     {
46         if(heap[i]<heap[1]) //如果遇到比堆顶元素小的元素，就更新堆
47         {
48             heap[1]=heap[i];
49             max_heapity(heap,1,k);
50         }
51     }
52     for(int j=1;j<=k;j++)
53         printf("%4d",heap[j]);
54 }