网站管理助手4.0教程,小型公司怎么注册,专门做杂志的网站有哪些,外贸开源网站目录 1.堆的概念
2.堆的构建
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个数据来建堆
6.…目录 1.堆的概念
2.堆的构建
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个数据来建堆
6.2.2剩下的N-K
6.3示例 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
#includeHeap.h
#includetime.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;
}
