这是《编程珠玑》中的一道题目。10亿个整数，假设每个整数需要四个字节，如果使用排序的话，需要大约4G的内存，现在的很多pc都没有多这么内存，更不用说作者那个年代。
我们借助最小堆来解决这个问题。

主要步骤

  • 使用一个大小为一百万零一的整数数组来构建堆（堆的下标从1开始）
  • 从文件中读取前一百万个数，每读入一个数，调用函数，保持其最小堆的性质，堆的根永远是堆中最小的元素。
  • 从一百万零一个数开始，每读入一个数开始，比较这个数与堆的根比较，如果比根大，就用这个数替换掉根，调用函数，保持最小堆性质。

先生成10亿个随机数，使用的也是《编程珠玑》上的方法，将这10亿个数输出到data.txt中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    unsigned m, n;
    printf ("生成m个小于等于n的随机数！，请输入m和n：\n");
    scanf("%d%d", &amp;m, &amp;n);

    FILE *fp = fopen("data.txt", "w");
    /* 生成m个小于等于n的随机数 */
    unsigned i;
    for(i = 0; i &lt; n; ++ i){
        int temp = rand();
        if((temp  % (n - i)) &lt; m){
            fprintf(fp, "%d\n", i);
            -- m;
        }
    }
    fclose(fp);

    return 0;
}

生成了10亿个小于20亿的随机数，并且这10亿个数是不重复的。整个data.txt文件大约有10G，我的系统无法打开，内存不够。
然后就是从这10亿个数中选出前100万个最大的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>

/* 定义堆的大小 */
#define HEAPSIZE 1000000
/* 使用数组来构建最小堆 */
unsigned num[HEAPSIZE+1];

/* 在堆的末尾插入新元素后，保持最小堆性质 */
void siftup(int size){
    int i = size;
    unsigned parent, temp;

    while(1){
        if(i == 1)
        break;

        parent = i / 2;
        /* 已经是最小堆，退出 */
        if(num[parent] <= num[i])
            break;

        /* 交换父亲和儿子 */
        temp = num[parent];
        num[parent] = num[i];
        num[i] = temp;

        i = parent;
    }
}

/* 替换根元素后保持最小堆性质 */
void siftdown(int size){
    int i = 1;
    unsigned child;

    while(1){
        child = 2 * i;
        if(child > size)
            break;

        /* child 是 i 的左儿子 */
        if(child + 1 <= size){
            /* 选取两个儿子中比较小的那个 */
            if(num[child+1] < num[child]){
                ++child;
             }
        }

        /* 已经是最小堆，退出 */
        if(num[i] <= num[child])
            break;

        /* 交换父亲和儿子 */
        unsigned temp;
        temp = num[i];
        num[i] = num[child];
        num[child] = temp;

        i = child;
    }
}

int main(int argc, char *argv[]) {

    FILE *fp = fopen("data.txt", "r");

    unsigned i, number;
    unsigned count = 0;
    while(fscanf(fp, "%d", &number) != EOF){
        /* 前100万个数构建最小堆 */
        if(count < HEAPSIZE){
            ++count;
            num[count] = number;
            siftup(count);
            continue;
        }

        /* 从100万零1个数开始，将当前数与根元素比较 */
        if(number > num[1]){
            num[1] = number;
            siftdown(count);
        }
    }
    fclose(fp);

    /* 将结果输出到文件中保存 */
    FILE *result_fp = fopen("result.txt", "w");

    for(i = 1; i <= HEAPSIZE; ++i){
        fprintf(result_fp, "%d\n", num[i]);
    }
    fclose(result_fp);

    return 0;
}

前100万个数使用siftup函数构建最小堆，而后的数与堆的根比较，如果比根大，则替换掉根，并使用siftdown函数保持最小堆性质。

(结束)