前言：本篇對TopK問題的解答是介于堆的基礎上講的
TopK問題：
就是在許多數據中找到前K個最大的數據或者最小的數據
比如：專業前10、世界五百強、富豪榜、以及游戲排行榜等等
對于TopK問題：能想到的最簡單直接的方式就是排序解決,通常包括排序、堆排序、快速選擇等排序算法，但是如果數據量太大了，排序就不太可能了（可能數據都不能一下子全部加載到內存中），用到堆排序的方法能夠大大減少計算時間和內存需求，反而能得到很高的效率
怎么做？
最開始第一想法肯定是，將所有數據建立成K個堆，然后將K個堆的堆頂元素Top（取）出來，得到的就是每個堆的最大/最小的元素，但是呢？這樣的話，需要的空間還是挺大的，那么有沒有其他辦法能夠做到，占用少量的空間，完成巨大的任務量呢？？
嘗試著以K個元素只建一個堆，空間減小了很多，由堆的性質，這個問題好像就迎刃而解了！我們將后n-k個數全部比較，每放進去一個元素又調整成堆，也就是每次堆頂元素都是最小值，堆頂元素（最小值）找到比他大的就會被Pop掉，當后N-K個元素比較完后，最后留在堆里的不就是最大的K個數么
?來實現一下10個最大的元素，這里我們用到rand函數和srand以及time生成隨機數，即將偽隨機變成隨機來創建一些數據來進行，當然為了驗證，自己可以在最后的數據加10個最大數據，驗證即可；這里建堆用的向下排序建堆，因為相比于向上排序建堆，時間復雜度更低
#define _CRT_SECURE_NO_WARNINGS 3
#include<stdio.h>
#include<stdlib.h>
#include<time.h>//交換函數
void Swp(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//打印：
void INPrin(int* a,int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}}
//向下調整：小堆
void AdjustDownSmall(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//假設法：誰小,小的孩子往上走//因為會有孩子沒有兄弟if (a[child] > a[child + 1] && child + 1 < n){child = child + 1;}if (a[child] < a[parent]){Swp(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void createndate()
{//造數據：int n = 10000;//設置種子：隨機數srand((unsigned int)time(NULL));//以寫的形式打開文件;FILE* fp = fopen("data.txt", "w");if (fp ==NULL){perror("fopen");return;}//數據個數:for (int i = 0; i < n; i++){//生產0-10000的隨機數int ret = (rand()+i) % n;fprintf(fp, "%d\n", ret);}//驗證for (int j = 3*n; j < 3*n + 11; j++){fprintf(fp, "%d\n", j);}fclose(fp);fp = NULL;
}
//top-k問題：得到最大的k個數
void printtopk(int k)
{//打開文件(讀)FILE* fp = fopen("data.txt", "r");if (fp == NULL){perror("fopen");return;}int* a = (int*)malloc(sizeof(int) * k);if (a == NULL){perror("malloc");return;}//int i;for (i = 0; i < k; i++){fscanf(fp, "%d", &a[i]);}//前k個建小堆：(向下調整)時間復雜度為：o(n)for (i = (k - 1 - 1) / 2; i > 0; i--){AdjustDownSmall(a, k, i);}int x = 0;while (fscanf(fp, "%d", &x) >0){//進行比較并xiangxia調整if (a[0] < x){a[0] = x;AdjustDownSmall(a, k, 0);}}INPrin(a, k);
}int main()
{//createndate();printtopk(10);return 0;
}?當然結果并非有序的，想讓它有序其實就是堆排序的操作，對這10個元素，不斷取棧頂元素，放到數組就能排序好
?x
感謝觀看，下次見
