【数据结构与算法】——堆（补充）

前言

上一篇文章讲解了堆的概念和堆排序，本文是对堆的内容补充
主要包括：堆排序的时间复杂度、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;
}