数据结构-堆的实现和应用
目录
1.堆的概念
堆的底层是数组，所以堆也是一种特殊的数组。
堆分为大堆和小堆
- 大堆：父节点不小于子节点
- 小堆：父节点不大于子节点
2.堆的构建
已经提到堆是一种数组，那么要怎么实现呢。
先以小堆为例，已知父节点不小于子节点，使用数组，数组下标0是根节点，1和2是他的子节点，接着1的子节点是3和4,2的子节点是5和6，这样就可以实现一个堆了。
3.堆的实现
既然是数组，就要有指针，容量大小。
4.堆的功能实现
4.1堆的初始化
4.2堆的销毁
4.3堆的插入
一直到这一步，都是和栈是相同的，因为我们插入数据了，这时我们无法保证这是一个堆，所以此时要进行向上调整。
4.3.1向上调整
因为此时插入是数据再最下面，所以要和上面的进行比较调整。
4.4堆的删除
我们是删除堆的最后一个元素，要怎么删除呢，我们可以将最后一个元素和第一个元素进行交换，然后使堆向下调整即可。
4.4.1向下调整法
4.5取堆顶
5. 向上调整法和向下调整法比较
推导时间复杂度，由于用图来表示有些难度，这里直接用笔写出来
这是向下调整法的推导过程
向下调整建堆的时间复杂度如图
下面是向上调整建堆的时间复杂度推导
总结:向上调整算法建堆是优于向下调整建堆的。
6.堆的应用
6.1TOP-K问题
这种问题通常是在较大的数据样本中取出其中的最值，这时就可以通过堆来完成。
通常这类问题样本较大，排序就不太可取，可以建堆来实现。
6.2TOP-K思路
6.2.1用前n个数据来建堆
求最大的前n个就建小堆
求最小的前n个就建大堆
6.2.2剩下的N-K
用剩下的N-K个数据来和堆顶数据比较，不满足就替换堆顶元素
6.3示例
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" #include<time.h> void test() { HP hp; HPInit(&hp); HPPush(&hp, 2); HPPush(&hp, 4); HPPush(&hp, 1); HPPush(&hp, 1); printf("%d", HPTop(&hp)); } void CreateNDate() { int n = 10000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (file == NULL) { perror("fopen fail"); return; } for (int i = 0; i < n; i++) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void topk() { int k = 0; printf("输入k的值\n"); scanf("%d", &k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); int* arr = (int*)malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { fscanf(fout, "%d", &arr[i]); } //建堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, i, k); } int x = 0; while (fscanf(fout, "%d", &x) != EOF) { if (x > arr[0]) { arr[0] = x; AdjustDown(arr, 0, k); } } for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } fclose(fout); } int main() { CreateNDate(); topk(); return 0; }
