海量數據 Top-K 問題：堆排序版從 N 個數選最大前 10 個完整實現

面試經典題：從 N 個數（N 可達 1000 億）選出最大的前 10 個有序輸出。本文提供基於**最小堆**的 C 語言完整實現，含測試數據生成、流式讀取、堆維護、統計分析，時間複雜度 O(N log K)，空間 O(K)。

算法核心思想

• 維護大小為 K=10 的最小堆（堆頂最小）
• 遍歷數據流：新數 > 堆頂 → 替換堆頂並下沉
• 最終堆內即為 Top-K，再堆排序輸出
• 流式處理，無需全量載入內存

完整代碼

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>

#define BUFF_LEN (4096)
#define PARENT(i) ((i) / 2 - 1)
#define LEFT(i)   ((i + 1) * 2 - 1)
#define RIGHT(i)  ((i + 1) * 2)

#ifdef INFO
    int s_0, s_1, s_2;
    struct timeval begin, end;
#endif

static void generate_test_data(long n) {
    long i; int r, l = sizeof(int);
    srand(time(NULL));
    for(i=0; i\n 2. Run Top10: %s exec\n", argv[0], argv[0]);
        return 0;
    }
    if(strcmp(argv[1], "exec") != 0) {
        generate_test_data(atoi(argv[1]));
        return 0;
    }
    
    sbuff = malloc(1024*1024*4 - 4);  // 4MB 輸入緩衝
    rbuff = malloc(256*1024*10*4);    // 結果緩衝
    rbuff_t = rbuff;
    
    #ifdef INFO { s_0=s_1=s_2=0; gettimeofday(&begin,NULL); }
    
    // 流式處理每個塊
    while((n = read_input(STDIN_FILENO, sbuff, 1024*1024*4 - 4)) != 0) {
        #ifdef INFO s_2 += n/4; #endif
        // 建堆
        for(j = (n/4)/2; j >= 0; j--) {
            #ifdef INFO s_0++; #endif
            max_heapify(sbuff, j);
        }
        // 取塊內 Top10 併入結果堆
        for(i=0; i<10; i++) {
            #ifdef INFO { s_0++; s_1+=4; #endif
            rbuff[rbuff_n] = sbuff[0];
            sbuff[0] = sbuff[n/4 - 1 - i];
            sbuff[n/4 - 1 - i] = -1;
            max_heapify(sbuff, 0);
            rbuff_n++;
        }
    }
    
    // 結果堆排序輸出
    for(j = rbuff_n/2; j >= 0; j--) {
        #ifdef INFO s_0++; #endif
        max_heapify(rbuff, j);
    }
    for(i=0; i<10; i++) {
        #ifdef INFO { s_0++; s_1+=4; #endif
        printf("%d\n", rbuff[0]);
        rbuff[0] = rbuff[rbuff_n - i];
        rbuff[rbuff_n - i] = -1;
        max_heapify(rbuff, 0);
    }
    
    #ifdef INFO {
        gettimeofday(&end,NULL);
        fprintf(stderr, "總計[%d]個輸入\n總計比較[%d]次\n總計寫內存[%d]次\n總計耗時[%0.6fs]\n",
            s_2, s_0, s_1, (end.tv_sec*1000000+end.tv_usec-begin.tv_sec*1000000-begin.tv_usec)/1000000.0);
    }
    return 0;
}

關鍵點解析

測試結果（100 萬輸入）

總計[1000000]個輸入
總計比較[4232804]次
總計寫內存[3849024]次
總計耗時[0.046478s]

編譯與運行

gcc -DINFO -o top10_heap top10_heap.c
# 生成測試數據
./top10_heap 1000000 2>data.bin | head -20
# 執行 Top10（管道輸入）
./top10_heap exec < data.bin

優化方向

• 改用 stdlib.h qsort 做塊內排序（常數因子更小）
• 結果堆用固定大小 10 陣列 + 插入排序（K=10 時更快）
• 多線程：MapReduce 風格分塊並行，歸併階段合併
• 外部排序：數據超內存時歸併排序落盤

複雜度對比

1. 上一篇文章： C語言實現函數重載：可變參數、GCC擴展、宏與函數指針四大方案
2. 下一篇文章： 海量數據 Top-K 問題：鏈表版從 N 個數選最大前 10 個完整實現

關於C

C語言字符串進階操作：刪除指定字符、去首字符、翻轉字符串

標準庫 <string.h> 提供了 strcp

C語言計算：本利和翻倍所需年數 (複利公式迭代法)

已知本金 a、年利率 x%，求存入銀行幾年後本利和達到 2a

HDU 2187 悼念 512：分數背包貪心購買大米

題目背景與模型 地震災區急需糧食，給定經費 n 和 m 種大

JCFXBL 輔助類：C# WinForms 數據綁定與數據庫交互封裝庫

項目定位 JCFXBL.API.Helper 是專為 C#