网站刷链接怎么做,沈阳好的互联网设计,长春关键词排名优化,没有网站也可以做cpa#x1f308;一、堆的基本概念
1.堆#xff1a;非线性结构#xff0c;是完全二叉树 2.堆分为大堆和小堆。 大堆#xff1a;树中任意一个父亲都大于等于孩子#xff0c;根节点值大于等于其所有子孙节点的值。 小堆#xff1a;树中任意一个父亲都小于等于孩子#xff0c;…一、堆的基本概念
1.堆非线性结构是完全二叉树 2.堆分为大堆和小堆。 大堆树中任意一个父亲都大于等于孩子根节点值大于等于其所有子孙节点的值。 小堆树中任意一个父亲都小于等于孩子根节点值小于等于其所有子孙节点的值。 3.“同辈”即同一层数据间的大小顺序不做要求。 4.堆的物理结构即实际内存中存储的结构是顺序表但逻辑结构是树。 5.堆特性堆中最有用的数据是堆的根节点。小堆的根是整棵树的最小值大堆的根是整棵树的最大值. 6.堆的用途①topk问题 ②堆排序
二、实现一个小堆大堆同理
☀️1头文件test.h:
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int HpDataType;
typedef struct {HpDataType* a;int size;int capacity;
}HP;
void Swap(HpDataType* p1, HpDataType* p2);
void AdjustUp(HpDataType* php, int x);
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HpDataType x);
void AdjustDown(HpDataType* a, int n, int parent);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
☀️2函数实现heap.c
1.初始化、销毁函数
#define _CRT_SECURE_NO_WARNINGS
#includetest.h
void HeapInit(HP* php) {assert(php);php-a NULL;php-size 0;php-capacity 0;
}
void HeapDestroy(HP* php) {assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}2.打印、交换数值函数
void Swap(HpDataType* p1, HpDataType* p2) {HpDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void HeapPrint(HP* php) {assert(php);for (int i 0;i php-size;i) {printf(%d , php-a[i]);}printf(\n);
}Swap函数细节分析 Swap函数用来交换父亲节点和孩子节点的值
3.插入、向上调整函数
现在有一个堆对其插入一个值 插入位置插入到根节点会破坏堆的结构插入到树的中间部分的话我怎么知道哪里是中间部分难不成还要先算一下树的大小只能插入到最高层的末尾位置即数组的末尾处然后一层一层向上调整成一个正确的堆。 步骤一首先需要判断该堆的容量是否足够插入一个节点容量不够就扩容。 步骤二根据插入的值判断是否需要对树进行调整。 eg该情况下若插入90不需要对树进行调整 若插入50需要对树进行调整 调整部位右子树即50的“祖先”不调整左子树15及其“子代”。 如何调整一层一层地和“父亲”换位置直到符合大小排序。 调整完的样子
代码部分 void AdjustUp(HpDataType* a, int child) {int parent (child - 1) / 2;//为什么要用循环//因为不止调整一次有可能调整好多次直到child走到了根节点while (child 0) {if (a[child] a[parent]) {swap(a[child], a[parent]);//为什么还要加取地址符号//因为要对该空间的值进行更改传值调用不会改变空间上的值只有传地址才行child parent;parent (child - 1) / 2;}elsebreak;}
}
void HeapPush(HP* php, HpDataType x) {assert(php);//步骤一扩容放值if (php-size php-capacity) {int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HpDataType* tmp (HpDataType*)realloc(php-a, sizeof(HpDataType) * newCapacity);if (tmp NULL) {perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;//步骤二调整//命名含义每次插入的位置都是最后一层最右边的节点//调整过程是一层一层向上进行的因此叫adjust upAdjustUp(php-a, php-size - 1);//函数参数//参数一需要知道在那棵树中调整数组指针即a//参数二需要知道调整哪个节点下标即size-1
}细节分析 1.关于AdjustUp函数名和参数 2.关于AdjustUp函数内部
4.删除、向下调整函数
删除位置基于堆的特性堆中最有用的数据是根上的数据因此删除也是删除根的数据。 如何删除 错误方法直接挪动后面的数据覆盖这样会破坏堆结构得到的不一定是堆如图 挪动覆盖根关系全乱了原先的兄弟关系被迫变成了父子或长辈晚辈关系不一定稳定不一定符合大小顺序就不一定是堆了。 正确方法最下面一层的最后一个数8和根位置的数据2交换然后删除掉最后一层最后一个数据–size就删除了然后从根节点向下调整。下一层的最小的数据和根数据交换直到走到最下面一层就调整成了正确的堆结构。每删除pop一次就能得到堆中最小的数。 背后原理不破坏树原本的结构左右子树依旧是小堆。 注 向下调整前提左右子树是堆 向上调整前提前面的数据是堆。
代码实现
void AdjustDown(HpDataType* a, int n, int parent) {int child parent * 2 1;//while循环作用1.实现从上到下一层一层调整 //2.childn时说明已经调整到最后一层停止循环while (child n) {//当有两个孩子时需要选出较小的孩子与父节点比较//如果只有一个孩子那child下标就是parent*21if (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;}//只要某一层的孩子节点值大于父节点值就停止循环//这是基于除了根节点其他地方都符合堆结构的前提elsebreak;}
}
void HeapPop(HP* php) {assert(php);assert(php-size 0);swap(php-a[0], php-a[php-size - 1]);--php-size;AdjustDown(php-a, php-size, 0);//参数分析//参数一结构体中的数组指针指向堆//参数二堆的大小计算出的孩子序号数与堆大小进行比较就可以知道是否有该孩子//参数三父节点下标从该位置开始向下调整
}细节分析关于AdjustDown函数 ①参数分析
②while循环作用
③孩子节点可能有一个或两个如何选出值较小的那个 当没有“child1n”条件时如果父节点只有一个左孩子那么a[child1]就会造成越界访问。
④向上调整或向下调整的前提是除了被调整节点其他部位都符合堆即左右子树是堆
5.根节点函数、判空函数
HpDataType HeapTop(HP* php) {assert(php);assert(php-size 0);return php-a[0];
}
bool HeapEmpty(HP* php) {assert(php);return php-size 0;
}☀️3测试test.c:
1.测试插入
测试思路一个数组本身不是堆但当我将每一个元素都push进去后它就变成了堆。通过打印看是否建堆成功。
#define _CRT_SECURE_NO_WARNINGS
#includetest.h
int main() {int a[] { 65,100,70,32,50,60 };HP hp;HeapInit(hp);for (int i 0;i sizeof(a) / sizeof(a[0]);i) {HeapPush(hp, a[i]);}HeapPrint(hp);HeapDestroy(hp);return 0;
}打印结果 从物理结构转变为逻辑结构建堆成功。
2.测试从小到大对堆中的值排序
测试思路先通过push函数将数组建成堆结构然后通过top函数得到根节点值最小值最后pop掉根节点将剩下的数调整成堆结构继续得到根节点值次小值。
#define _CRT_SECURE_NO_WARNINGS
#includetest.h
int main() {int a[] { 65,100,70,32,50,60 };HP hp;HeapInit(hp);for (int i 0;i sizeof(a) / sizeof(a[0]);i) {HeapPush(hp, a[i]);}HeapPrint(hp);while (!HeapEmpty(hp)) {printf(%d , HeapTop(hp));HeapPop(hp);}HeapDestroy(hp);return 0;
}打印结果 由此可以看出将一组数据建堆是对改组数据进行粗略的排序将堆的根一个一个取出才能得到准确的大小关系。
思考如何实现大堆
AdjustUp函数和AdjustDown函数中把if中的大于小于号换一下即可。
三、堆结构基础上实现堆排序
给出一个数组将数组中的数据一个一个放进搭建好的小堆结构中再将每次pop出来的最小值根节点数据从左到右放进原数组从而排成升序。
☀️HeapSort函数
void HeapSort(int* a, int n) {HP hp;HeapInit(hp);for (int i 0;i n;i) {HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)) {a[i] HeapTop(hp);HeapPop(hp);}HeapDestroy(hp);
}测试将一组数排成升序
int main() {int a[] { 2,3,5,7,4,6,8,65,100,70,32,50,60 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}结果通过监视看内存 思考如果要将改组数据排成降序呢 法一得到pop出来的最小值根节点后从原数组最后面往前放置。 法二建大堆将每次pop出的最大值根节点从前往后放进原数组。 注这种写法的缺陷 1.需要先搭建一个完整的堆结构先初始化再有插入向上调整删除向下调整等等 2.空间复杂度的消耗被排序的原数组占据了一部分空间将原数组的值插入进堆中又占用了相同大小的空间造成空间浪费。
四、无堆结构在数组上原地建堆
☀️法一向上调整建堆
1.思路从前往后依次将数组的值插入进堆并向上调整。不需要初始化与销毁只需要AdjustUp函数。 2.代码 heap.c函数文件:
void AdjustUp(int* a, int child) {int parent (child - 1) / 2;while (child 0) {if (a[parent] a[child]) {Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
void HeapSort(int* a, int n) {for (int i 0;i n;i) {AdjustUp(a, i);}
}test.c测试文件: 测试将一组数组中的无序的数排成小堆
#define _CRT_SECURE_NO_WARNINGS
#includetest.h
int main() {int a[] { 70,65,100,32,50,60 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0;i sizeof(a) / sizeof(int);i) {printf(%d , a[i]);}
}测试结果 原地建堆成功。
☀️法二向下调整建堆
1.思路从最后一个节点的父节点倒数第一个父节点开始向下调整至正确大小顺序然后指针向前移动指向倒数第二个父节点向下调整直至从根节点向下调整。 2.代码 heap.c函数文件:
void AdjustDown(int* a, int size,int i) {int parent i;int child parent * 2 1;while (child size) {if (child 1 size a[child] a[child 1]) {child;}if (a[parent] a[child]) {Swap(a[parent], a[child]);parent child;child parent * 2 1;}elsebreak;}
}
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
void HeapSort(int* a, int n) {for (int i (n - 1 - 1) / 2;i 0;i--) {AdjustDown(a, n, i);}
}细节 为何有child1size没有的话会怎样
堆的节点不一定都有两个孩子如果倒数第一个父节点只有一个左孩子则child1就越界了。因此要确保有两个孩子的情况下才能比较两个孩子谁大谁小只有一个孩子时child就储存这一个孩子节点的下标。 test.c测试文件: 测试将一组数组中的无序的数排成小堆
#define _CRT_SECURE_NO_WARNINGS
#includetest.h
int main() {int a[] { 70,65,100,32,50,60 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0;i sizeof(a) / sizeof(int);i) {printf(%d , a[i]);}
}测试结果
☀️比较向上和向下调整建堆
1.计算向下调整建堆时间复杂度O(N)N-logN
2.向上调整建堆时间复杂度N*logN 3.比较结果向下调整时间复杂度更低效率更高。 更直观的理解方法对于向上调整而言节点最多的那一层最高层需要向上调整的次数最多有h层就调整h-1次即大数乘大数对于向下调整而言节点最多的那一层最高层需要向下调整的次数最少最高层调整0次即大数乘小数。因此相比较而言向下调整建堆时间复杂度更低。
五、无堆结构对数组进行堆排序
思路先通过向上或向下调整建堆在没有堆结构的基础上让数组先成为堆再通过pop的思想每次得到根节点即为当前的最大值最小值。步骤为建堆-pop。
☀️升序降序分别建什么堆
假设现在要将一组数排成升序 如果在已经有堆结构的基础上排升序法一是建小堆pop出来的数是从小到大的从左到右排列在新开辟的数组空间中从而将数组排成升序。法二是建大堆pop出来的数是从大到小的只需要从空间的右边往左边排即可排成降序。
现在没有堆结构并且直接在原数组上建堆意味着不可以新开辟空间此时需要仔细斟酌排序对应建什么堆 1.错误方法排升序建小堆 第一步建成小堆后得到物理结构与逻辑结构如下 第二步pop出根节点得到最小值32并且刚好在数组最左边。 第三步用剩下的数据得到次小值。 问题来了如何排除掉第一个数据 如果直接移动指针将下标为1的节点作为根节点则有破坏堆结构的风险如图 如果将剩下的数重新建堆则代价太大。 因此排升序不可以建小堆。 2.正确方法建大堆每次pop出的数和数组最右边一个数交换再向下调整从而得出次大的数从右往左放置从大到小的数从而排成升序。 具体过程如下 3.结论排升序建大堆排降序建小堆。 4.为何有堆结构时可以随意建大小堆无堆结构时有限制 本质上是因为有堆结构时可以将数据从原先的混乱数组中转移到一片新的空间只需要将大小堆和放置先后顺序匹配就可排成任意顺序排升序如果建大堆从右往左放如果建小堆从左往右放排降序如果建大堆从左往右放如果建小堆从右往左放。无堆结构时从混乱的一组数据到堆结构再到有序结构始终是在同一块空间上进行操作的为了不破坏堆结构只能用pop和向下调整的方式因此对什么时候建什么堆有限制升序建大堆降序建小堆。
☀️代码将数组排成降序
方法让数组中的数据一个一个插入到堆的最后面再向上调整从而建堆。
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
void AdjustDown(int* a, int size, int i) {int parent i;int child parent * 2 1;while (child size) {if (child 1 size a[child] a[child 1]) {child;}if (a[parent] a[child]) {Swap(a[parent], a[child]);parent child;child parent * 2 1;}elsebreak;}
}void HeapSort(int* a, int n) {for (int i (n - 1 - 1) / 2;i 0;i--) {AdjustDown(a, n, i);}int end n - 1;while (end 0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
int main() {int a[] { 70,65,100,32,50,60 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0;i sizeof(a) / sizeof(int);i) {printf(%d , a[i]);}
}测试结果
☀️应用TopK问题
问题背景一共10000个数要找出最大的前10个。 程序设计 1.随机生成10000个值小于10000的数 2.随机10挑个数改成大于10000的值为了方便检查测试结果,如果最终得到的10个数就是这些大于10000的值的话则说明筛选成功 解决方案 先对这10000个数的前10个数建小堆然后后面的9990个数依次和堆顶数据比较大于堆顶数据的话则顶替这个堆顶数据进堆。 问为何要对前10个数据建小堆建大堆会怎样 答假设这10000个数中最大的数恰好在前10个中则建了大堆后根节点一开始的值就是最大值后面的9990个数就无法进堆最终只有根节点的最大值是准确的剩下的9个值找不到。而建小堆的话最大的前10个数来了都可以畅通无阻的进堆然后再向下调整至正确位置最终堆中剩下的数就是最大的前10个。
代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include string.h
#includetime.h
#includestdlib.h
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
void AdjustDown(int* a, int k, int parent) {int child parent * 2 1;while (childk) {if (child 1 k a[child 1] a[child]) {child;}if (a[parent] a[child]) {Swap(a[parent], a[child]);parent child;child parent * 2 1;}else {break;}}
}
void PrintTopK(int* a, int n, int k) {//对前10个数据建小堆for (int i (k-2)/2;i 0 ;i--) {AdjustDown(a, k, i);}//将剩下9990个数据依次与堆顶元素比较//若大于堆顶则替换堆顶进堆并向下调整for (int i 0;i n - k;i) {if (a[k i] a[0]) {Swap(a[k i], a[0]);AdjustDown(a, k, 0);}}//将前k个数据打印出来for (int i 0;i k;i) {printf(%d , a[i]);}
}
void TeatTopK() {int n 10000;int k 10;srand(time(0));int* a (int*)malloc(sizeof(int) * n);for (size_t i 0;i n;i) {a[i] rand() % 10000;}a[10] 10001;a[29] 10002;a[300] 10003;a[790] 10004;a[1440] 10005;a[4990] 10006;a[6900] 10007;a[6930] 10008;a[8999] 10009;a[9999] 10010;//先展示一下最初始的前10个数for (int i 0;i k;i) {printf(%d , a[i]);}printf(\n);//再展示筛选出来的前10个数PrintTopK(a, n, k);
}
int main() {TeatTopK();
}测试结果 由于不对前10个最大的数有顺序要求因此每次运行完程序得到的前10个数的顺序不一样。
