前言

上一篇文章講解了堆的概念和堆排序，本文是對堆的內容補充
主要包括：堆排序的時間復雜度、TOP

正文

堆排序的時間復雜度

前文提到，利用堆的思想完成的堆排序的代碼如下（包含向下調整）：

#include <stdio.h>// 交換兩個整數的值
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}// 大頂堆向下調整
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1; // 左孩子while (child < n){// 保障右孩子存在且右孩子更大if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){// 調整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆排序
void HeapSort(int* arr, int n)
{// 建堆——向下調整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}// 堆排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}// 打印數組
void PrintArray(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{int arr[] = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的數組: ");PrintArray(arr, n);HeapSort(arr, n);printf("排序后的數組: ");PrintArray(arr, n);return 0;
}

那么我們如何計算他的時間復雜度呢？
1.建堆過程
堆排序的算法中，首先先是向下調整算法

需要移動結點總的移動步數為：每層結點個數*向下調整次數
列式為：

很明顯，這是高中學過的等比數列，利用錯位相減法可以算出T（n）
結果是：

向下調整算法建堆時間復雜度為：O(n)

同樣我們可以算出向上排序的時間復雜度為：

向上調整算法建堆時間復雜度為：O(n ? log2n)

堆排序的時間復雜度為 O(n log n)，以下是具體分析：

排序階段
每次將堆頂元素（最大值）與堆尾元素交換，然后對剩余 (n-1, n-2, \dots, 1) 個元素重新調整堆。每次調整堆的時間為 (O(log n))（堆的高度為 (log n)），共進行 (n-1) 次交換和調整，總時間為

最后匯總
建堆階段 (O(n)) 和排序階段 (O(n \log n)) 中，(O(n \log n)) 是主導項，因此堆排序的總時間復雜度為 (O(n log n))。

TOP-K

TOP-K問題：即求數據結合中前K個最?的元素或者最?的元素，?般情況下數據量都?較?。
比如崩壞 星穹鐵道活躍度最高的240萬個玩家（這只是例子）
對于Top-K問題，能想到的最簡單直接的?式就是排序，但是：如果數據量?常?，排序就不太可取了
(可能數據都不能?下?全部加載到內存中)。最佳的?式就是?堆來解決，基本思路如下：

1）?數據集合中前K個元素來建堆
前k個最?的元素，則建?堆
前k個最?的元素，則建?堆
2）?剩余的N-K個元素依次與堆頂元素來?較，不滿?則替換堆頂元素
將剩余N-K個元素依次與堆頂元素?完之后，堆中剩余的K個元素就是所求的前K個最?或者最?的元素

代碼如下
1.先把前面學過的代碼拿過來，這里剛好可以復習一下如何用向下調整法建堆

//求最大k個數
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>//堆的結構
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;    //有效數據個數int capacity;//空間大小
}HP;void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//保障右孩子if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){//調整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.這里沒有數據，我們先創造100000個隨機數

void CreatNdata()
{//造數據int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!");return;}for (int i = 0; i < n; i++){int x = (rand() + 1) % n;fprintf(fin, "%d\n", x);}fclose(fin);
}

并且建立“data.txt”文本文件存放，，該文件位置與代碼位置一致，打開方法為
右擊文件名

點這個

就可以看到這個文件了，選擇記事本打開

3.具體寫法
1） 輸入k值
2）以只讀的形式打開文件
3）動態分布一個大小為k的數組
4）先讀到k個數據并存到minheap[]

• 運用 fscanf 函數從文件中讀取前 k 個整數，并將它們存儲到 minheap 數組里。
• 從最后一個非葉子節點開始，通過AdjustDown函數對這 k 個數據進行調整，構建一個最小堆。
  5)讀取剩余元素并更新最小堆
• 利用 while 循環持續從文件中讀取剩余的數據，直到文件結束（EOF 表示文件結束）。
• 對于每個讀取到的數 x，若它比堆頂元素 minheap[0] 大，就把堆頂元素替換為 x，接著調用 AdjustDown 函數重新調整堆，保證堆仍然是最小堆。

6）關閉文件

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 fail");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, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){//讀取剩余的數據，誰比堆頂大，就替換它進堆if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");fclose(fout);
}int main()
{CreatNdata();topk();return 0;
}

最小值代碼

//求最小幾個數
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>// 堆的結構
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;    // 有效數據個數int capacity; // 空間大小
}HP;// 交換兩個整數的值
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}// 大頂堆向下調整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1; // 左孩子while (child < n){// 保障右孩子存在且右孩子更大if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){// 調整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 生成隨機數據并保存到文件
void CreatNdata()
{// 造數據int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail!");return;}for (int i = 0; i < n; i++){int x = (rand() + 1) % n;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* maxheap = (int*)malloc(sizeof(int) * k);if (maxheap == NULL){perror("malloc fail");return;}// 讀取前k個數據for (int i = 0; i < k; i++){fscanf(fout, "%d", &maxheap[i]);}// 建立k個數據的大頂堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(maxheap, i, k);}int x = 0;//修改后while (fscanf(fout, "%d", &x) != EOF){// 讀取剩余的數據，誰比堆頂小，就替換它進堆if (x < maxheap[0]){maxheap[0] = x;AdjustDown(maxheap, 0, k);}}// 輸出最小的k個數for (int i = 0; i < k; i++){printf("%d ", maxheap[i]);}printf("\n");fclose(fout);free(maxheap);
}int main()
{CreatNdata();topk();return 0;
}