top K問題（借你五分鐘）

前言

top K問題

模擬數據

建堆

驗證（簡單了解即可）

最終代碼

調試部分

前言

在大小堆的實現（C語言）中我們討論了堆的實際意義，在看了就會的堆排序（C語言）中我們完成了堆排序，在這一篇中我們會接著完成堆的第二個實際意義：top K問題，本篇中涉及的關于文件操作函數fprintf、fclose請查看：文件操作函數---C語言版本，本篇中涉及的關于隨機數函數time、rand、srand的使用請查看：time、rand和srand函數及應用（C語言）

top K問題

問題描述：獲取N個數里找最大的前K個數（N遠大于K）

解決思路一：

N個數插入進大堆中，Pop K次

時間復雜度：N*logN + K*logN == O(N*logN)

但如果N為100億（100億個整數需要40GB左右的內存空間），而只要查找前10個數（K為10）？?

解決思路二：

1、取前K個值，建立K個數的小堆

2、再讀取后面的值，跟堆頂元素比較，若大于堆頂元素，交換二者位置然后重新堆化成小堆，若不大于堆頂元素則不進堆，進行下一次的比較（重要）

時間復雜度：O(N*logK)

注意事項：必須要建立小堆，不能建立大堆，如果建立大堆，一旦第一大的數字在建堆時位于堆頂，后續第n大的數字就無法進堆，同時第二大的數字可能還會被擠出去，如果不信可以用[4,6,1,2,8,9,5,3]這個我隨機想出來數組用以上方法取前三個最大的數字試一試

? ? ? ? 有時候你可能會很想刨根問底的知道這些辦法都是怎么想出來的，其實我也不知道，這就跟你騎自行車的時候去思考這些鏈子為什么要這樣組合在一起，為什么組合在一起就可以產生這樣的效果，其實我們根本不需要思考那么多，我們只需要騎上自行車去干我們要干的事情即可，它只是一個用于解決我們問題的工具，我們說的解題思路也是一樣的，這些東西都是哪些很nb的人發明出來的，如果你是一個很nb的人你也不會看到這里不是，前人栽樹后人乘涼，作為一個還沒有完全深入學習數據結構的菜鳥既然已經知道了有這種解決辦法那么你就直接用，等你什么時候感覺自己已經很nb了再來思考為什么吧......（當然也不是說都不要思考一些必要的思考還是需要的）別鉆牛角尖了🤡

模擬實現：

使用數組[7, 8, 15, 4, 20, 23, 2, 50]演示如何使用最小堆找出前3個最大的元素。

首先，我們創建一個小堆，并將數組的前3個元素[7, 8, 15]插入堆中，初始堆的表示如下：
? ? ? ?7/ ? \8 ? ? 15
接下來遍歷數組，發現 4 < 7，因此我們不做任何操作

繼續遍歷數組，發現 20 > 7，因此將 7 替換為 20 并重新堆化成小堆
? ? ? ?8/ ? \20 ? ?15
繼續遍歷數組，發現 23 大于 8，因此我們將 8 替換為 23 并重新堆化成小堆
? ? ? ?15/ ? ?\20 ? ? 23
繼續遍歷數組，發現 2 < 15，因此我們不做任何操作

繼續遍歷數組，發現 50 > 15，因此我們將 15 替換為 50 并重新堆化成小堆
? ? ? ?20/ ? ?\50 ? ? 23
最后，數組遍歷完成，得到了最終的小堆
? ? ? ?20/ ? ?\50 ? ? 23
此時，堆中的前3個最大元素為 `[20, 50, 23]`，它們就是原數組中的前3個最大元素

模擬數據

1、利用srand、time、rand函數生成10000000個隨機數據并寫入data.txt文件中

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <time.h>
#include <windows.h>
#include <stdlib.h>//造數據
void CreatNData()
{int n = 10000000;srand(time(0));//造數據FILE* pf = fopen("data.txt", "w");if (pf == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(pf, "%d\n", x);}fclose(pf);
}int main()
{CreatNData();return 0;
}

關于“i”的解釋：使用變量?i?可以在每次生成隨機數時引入一個不同的偏移量，從而避免產生重復的隨機數序列。如果沒有這個偏移量，相同的?rand()?調用將始終得到相同的結果。通過引入一個變化因子（如?i）來修改隨機數生成過程可以增加隨機性，并且在循環或多次調用中產生不同的結果。這對于某些應用場景（例如密碼學、模擬和游戲等）可能非常重要，因為它們需要高度不確定性和獨立性，簡單來講就是防止生成的隨機數重復。

建堆

1、獲取指向存放了一千萬個隨機整數的文件地址

2、由于vs2022不支持C99的變長數組，所以需要手動申請k個空間用于建堆

3、讀取文件中的前k個數據，利用向上調整函數模擬堆插入的過程建堆

4、利用while循環，從第k+1個數開始（因為前面已經用fscanf函數讀取了前k個數）逐個讀取文件中的數字，直到讀取到文件末尾，讀取成功的值會被賦值給指定的變量x，然后將x與此時堆頂元素也就是數組的首元素比較，如果該元素大于堆頂元素就讓該元素進堆，并進行向下調整，確保小堆的性質不會改變

5、讀取完畢后，打印數組前k個元素，即打印堆的前k個結點

//打印前k個數
void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//建有k個數的小堆int* a = (int*)malloc(sizeof(int) * k);if (a == NULL){perror("melloc error");return;}//讀取前k個數，建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &a[i]);AdjustUP(a, i);}//調堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > a[0]){a[0] = x;AdjustDown(a, k, 0);}}//打印堆for (int i = 0; i < k; i++){printf("%d ", a[i]);}printf("\n");fclose(fout);
}

關于”fscanf(fout, "%d", &x)“的解釋：fscanf函數允許從指定文件流中按照指定格式讀取數據，并將其賦值給相應變量，通俗來講就是：每次調用?fscanf?函數都會嘗試從文件中讀取一個數據項，并根據提供的格式進行解析和賦值，如果希望實現循環逐個讀取文件中的多個數據項，需要結合循環語句來重復調用?fscanf?函數。

驗證（簡單了解即可）

????????為了檢驗我們選出是否真的是1~10000000的隨機整數，我們可以通過將文件中隨意的五個數改為五個間諜數：10000001、10000002、10000003、10000004、10000005，然后再次程序：

只列舉出來一個10000004，其余的都有?

可以看到五個大于10000000的間諜數成功的被選出來了，

解釋：因為我們之前選的數都是1~10000000之間的隨機整數，我們不確定選的數到底有沒有超出這個范圍，所以可以找幾個剛好緊挨10000000的間諜數，如果超過了

最終代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <windows.h>
#include <stdlib.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  //指向存儲元素的指針int capacity;	//當前順序表容量int size;		//當前順序表的長度
}HP;//交換父子位置
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上調整，此時傳遞過來的是最后一個孩子的元素下標我們用child表示
void AdjustUP(HPDataType* a, int child)
{//由于我們要調整父親與孩子的位置所以此時也需要父親元素的下標，而0父親元素的下標值 = （任意一個孩子的下標值-1）/ 2 int parent = (child - 1) / 2;//當孩子等于0的時位于樹頂（數組首元素的位置），樹頂元素沒有父親，循環結束while (child > 0){//如果孩子還未到頂且它的下標對應的元素值小于它的父親的下標對應的元素值，就將父子位置交換，交換玩后還要將下標對應的值“向上移動”if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}//由于這是一個小堆，所以當孩子大于等于父親時不需要交換，直接退出循環即可else{break;}}
}//向下調整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根據之前的推論，左孩子的下標值為父親下標值的兩倍+1，左孩子的下標值為父親下標值的兩倍+2int child = parent * 2 + 1;//循環結束的條件是走到葉子結點while (child < size){//假設左孩子小，若假設失敗則更新child，轉換為右孩子小，同時保證child的下標不會越界//if (child + 1 < size && a[child + 1] < a[child])，它也是if (child + 1 < size && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){//如果此時滿足孩子小于父親則交換父子位置，同時令父親的下標變為此時的兒子所在下標，兒子所在下標變為自己的兒子所在的下標（向下遞歸）Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//如果父親小于等于左孩子就證明刪除后形成的新堆是一個小堆，不再需要向下調整算法，循環結束else{break;}}
}//造數據
void CreatNData()
{int n = 10000000;srand(time(0));//造數據const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//打印前k個數
void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//建有k個數的小堆（由于vs2022不支持C99的變長數組，所以這里需要手動malloc建堆）int* a = (int*)malloc(sizeof(int) * k);if (a == NULL){perror("melloc error");return;}//讀取前k個數，建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &a[i]);AdjustUP(a, i);}//調堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > a[0]){a[0] = x;AdjustDown(a, k, 0);}}//打印堆for (int i = 0; i < k; i++){printf("%d ", a[i]);}printf("\n");fclose(fout);
}int main()
{//CreatNData();PrintTopK("data.txt",5);return 0;
}