经典笔试题：从十亿个整数中选择前100大整数的算法实现

最近几天都在研究一些面试，笔试题，发现有一种题型很经常出现，如从十亿个整数中选择前100大整数，或者是这类题的变形：

很多人看到这种题的第一反应是排序，如果你是这样回答的话，offer肯定是没有了。原因如下：

1.　　存放10亿个数据的内存得多大呀， 所以内部排序是不可能了！

2.　　就算采用外部排序的方法，可以解决内存不足的问题，但外部排序读取内存非常频繁，将大大影响速度，我怀疑计算机在报废之前，拍完序的可能性！

好了，说说我的方案吧！是我目前能想到的最好的方法，如果谁有更好的，欢迎分享呀！

1.　　用10亿个数据的前100个整数建立小顶堆。

2.　　向堆中插入数据，如果比堆顶小的话，直接抛弃。否则替换堆顶，进行堆调整。

3.　　当上面的操作完成后，堆里面的数据就是前100大的整数了。

上面的方法，读取文件的次数为10亿次（这是不可避免的），使用的内存为100个整数空间，最坏情况下的时间复杂度为(10亿*log(100)).

代码如下：

/*
 *开 发 者：卡农
 *开发时间：2010-10-5
 *描    述：从十亿个整数中选择前100大的算法实现
 */

#include<iostream>
using namespace std;

/*
 *小顶堆
 */
typedef struct {
        int data[100];
        int size;
}Heap;

/*
 *用前100个整数初始化小顶堆
 *参数：   data    100个整数
 *返回：   指向小顶堆的指针
 */
Heap * initHeap(int _data[]){
        Heap * newHeap=new Heap;
        newHeap->size=100;
        for(int i=0; i<100; i++){
                newHeap->data[i]=_data[i];
        }

        //调整为小顶堆
        for(i=100/2; i>=0; i--){
                int curPos=i;
                while(curPos<100){
                        if(curPos*2+1>=100){
                                break;
                        }

                        if(curPos*2+2>=100){
                                if(newHeap->data[curPos*2+1]<newHeap->data[curPos]){
                                        int temp=newHeap->data[curPos*2+1];
                                        newHeap->data[curPos*2+1]=newHeap->data[curPos];
                                        newHeap->data[curPos]=temp;
                                }
                                break;
                        }

                        if(newHeap->data[curPos*2+1]<newHeap->data[curPos*2+2]){
                                if(newHeap->data[curPos*2+1]<newHeap->data[curPos]){
                                        int temp=newHeap->data[curPos*2+1];
                                        newHeap->data[curPos*2+1]=newHeap->data[curPos];
                                        newHeap->data[curPos]=temp;
                                }
                                curPos=curPos*2+1;
                        }else{
                                if(newHeap->data[curPos*2+2]<newHeap->data[curPos]){
                                        int temp=newHeap->data[curPos*2+2];
                                        newHeap->data[curPos*2+2]=newHeap->data[curPos];
                                        newHeap->data[curPos]=temp;
                                }
                                curPos=curPos*2+2;
                        }
                }
        }

        return newHeap;
}

/*
 *向堆中插入数据，如果比堆顶小的话，直接抛弃。否则替换堆顶，进行堆调整。
 *参数：   _heap   小顶堆
 *                      value   数据
 */
void insertValue(Heap * _heap , int value){
        if(value<=_heap->data[0]){
                return;
        }

        _heap->data[0]=value;
        int curPos=0;
        while(curPos<100){
                if(curPos*2+1>=100){
                        break;
                }

                if(curPos*2+2>=100){
                        if(_heap->data[curPos*2+1]<_heap->data[curPos]){
                                int temp=_heap->data[curPos*2+1];
                                _heap->data[curPos*2+1]=_heap->data[curPos];
                                _heap->data[curPos]=temp;
                        }
                        break;
                }
                
                if(_heap->data[curPos*2+1]<_heap->data[curPos*2+2]){
                        if(_heap->data[curPos*2+1]<_heap->data[curPos]){
                                int temp=_heap->data[curPos*2+1];
                                _heap->data[curPos*2+1]=_heap->data[curPos];
                                _heap->data[curPos]=temp;
                        }
                        curPos=curPos*2+1;
                }else{
                        if(_heap->data[curPos*2+2]<_heap->data[curPos]){
                                int temp=_heap->data[curPos*2+2];
                                _heap->data[curPos*2+2]=_heap->data[curPos];
                                _heap->data[curPos]=temp;
                        }
                        curPos=curPos*2+2;
                }
        }
}

/*
 *打印小顶堆里面的数据
 *参数：   _heap   小顶堆
 */
void showHeap(Heap * _heap){
        cout<<"堆内部的数据："<<endl;
        for(int i=0; i<_heap->size; i++){
                if(i%10==0){
                        cout<<endl;
                }
                cout<<_heap->data[i]<<"\t";
        }
        cout<<endl;
}

/*
 *销毁顶堆
 *参数：   _heap   小顶堆
 */
void destoryHeap(Heap * _heap){
        delete(_heap);
}

/*
 *测试入口
 */
int main(){
        int array[100];
        //打开存储10亿数的文件
        FILE * input=fopen("C:\\Users\\kanong\\Desktop\\data.txt","r");
        if(input==NULL){
                cerr<<"can't open file!"<<endl;
                exit(1);
        }

        //先用文件的前面100个数据构建小顶堆
        int temp;
        int i=0;
        while(fscanf(input , "%d" , &temp)!=EOF&&(i<100)){
                array[i++]=temp;

        }
        Heap * newHeap=initHeap(array);
        
        //将文件后面的数据插入小顶堆
        while(fscanf(input , "%d" , &temp)!=EOF){
                insertValue(newHeap , temp);
        }

        //打印前100大的整数
        showHeap(newHeap);
        destoryHeap(newHeap);

        fclose(input);
        return 0;
}