目錄

TopK問題：

定義：

應用場景：

搜索引擎：

推薦系統：

數據分析：

數據挖掘：

TopK問題初階：（數據量較小情況）

TopK問題進階：（數據量較大情況）

堆排序：

堆排序排升序：

建小堆：

建大堆：

堆排序排降序：

建大堆：

建小堆：

---

TopK問題：

定義：

TopK問題即求數據集合中前K個最大的元素或者最小的元素。

應用場景：

搜索引擎：

在搜索引擎中，TopK問題可以用于返回用戶查詢的前K個最相關的搜索結果

推薦系統：

在電子商務網站或媒體流推薦中，可以使用TopK問題來提供用戶最感興趣的產品或內容。

數據分析：

在大數據分析中，TopK問題可用于查找最頻繁出現的元素或最高價值的數據點。

數據挖掘：

在聚類和分類問題中，可以使用TopK問題來選擇具有最高重要性的特征或數據點。

TopK問題初階：（數據量較小情況）

假設從M中個數據選出前N個大的（小的）數據，需要先對M個數據建堆，對于堆結構使用取堆頂數據算法（HeapTop）再將最后一個元素移到第一個元素的位置，再使用向上調整（Adjustup）/向下調整算法（Adjustdown），不斷執行這個過程N次，便可得到前N個大的（小的）數據。

void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void Adjustdown(HeapDataType* a, int n, int parent)
{size_t child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}HeapDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}

TopK問題進階：（數據量較大情況）

TopK問題初階的解決方法僅適用于M小的情況，如果M的數據量較大，則TopK問題初階算法不再試用。假設M為10億，對于M數據量建堆需要消耗約40個G的內存，此時內存不夠用，可以使用硬盤存儲，但還有更加簡單的方法。

可以先對前N個數據建堆，若想取出前N個大的數據，則應該建立小堆，將后續的（M-N）個數據不斷與堆頂數據進行比較，如果數據大于堆頂元素，則將數據與堆頂元素進行交換，并使用向下調整算法使堆保持小堆結構，最后小堆內剩下的N個數據就是M個數據內想取出的前N個數據。

若想取出前N個小的數據，則應該建立大堆，將后續的（M-N）個數據不斷與堆頂數據進行比較，如果數據小于堆頂元素，則將數據與堆頂元素進行交換，并使用向下調整算法使堆保持大堆結構，最后大堆內剩下的N個數據就是M個數據內想取出的前N個數據。

時間復雜度：N+（M-N）logK—>N

void CreateNDate()
{// 造數據int n = 100000;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) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//前k個數據為例
void topk()
{printf("請輸入k：>");int k = 0;scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int val = 0;int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 建k個數據的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minheap, k, i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){// 讀取剩余數據，比堆頂的值大，就替換他進堆if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}fclose(fout);}

堆排序：

堆排序排升序：

建小堆：

堆頂元素即為整個數據內最小元素，但后部元素只有孩子大于父親的關系，沒有孩子與孩子之間的關系，所以如果使用建小堆實現堆排序升序則需對于剩下的元素再進行建堆。

時間復雜度為N*logN

void HeapSort(int* a, int n)
{// a數組直接建堆 O(N)for (int i = (n-1-1)/2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

建大堆：

對于整個數據建立大堆，將堆頂元素與最后一個元素調換位置，此時最大的元素就處于正確的位置，再對于除去最后一個元素的剩余元素進行向下調整選出次大的數據，不斷重復此過程即可完成堆結構元素數據的升序排序。

堆排序排降序：

建大堆：

堆頂元素即為整個數據內最大元素，但后部元素只有孩子小于父親的關系，沒有孩子與孩子之間的關系，所以如果使用建大堆實現堆排序升序則需對于剩下的元素再進行建堆。

時間復雜度為N*logN

建小堆：

對于整個數據建立小堆，將堆頂元素與最后一個元素調換位置，此時最小的元素就處于正確的位置，再對于除去最后一個元素的剩余元素進行向下調整選出次小的數據，不斷重復此過程即可完成堆結構元素數據的升序排序。