建设信用卡银行积分商城网站,建设网站需要的资金清单,织梦网站一级目录,网页浏览器历史记录恢复我们本期来讲解堆结构
目录
堆的结构
堆的初始化
堆的销毁
堆的插入
向上调整算法
堆的删除
向下调整算法
取堆顶元素
判断堆是否为空
堆中元素个数 堆排序
向下调整与向上调整效率计算
Top-K问题
全部代码 堆的结构
堆是一种用数组模拟二叉树的结构 逻辑结构是…我们本期来讲解堆结构
目录
堆的结构
堆的初始化
堆的销毁
堆的插入
向上调整算法
堆的删除
向下调整算法
取堆顶元素
判断堆是否为空
堆中元素个数 堆排序
向下调整与向上调整效率计算
Top-K问题
全部代码 堆的结构
堆是一种用数组模拟二叉树的结构 逻辑结构是我们想象出来的物理结构是实实在在存在的
因为是用数组来实现的所以我们访问时访问的是下标那怎么通过下标来对应关系呢
孩子和父节点的关系为parent(child-1)/2leftchildparent*21rightchildparent*22
这样我们就可以将节点之间的关系对应起来了 数组存储只适合存储完全二叉树如果不是完全二叉树就会出现很多空的地方会有很大的空间浪费 我们主要掌握两种结构一种是小堆一种是大堆 小堆是所有的父亲都小于等于孩子大堆是所有父亲大于等于孩子
接着我们就来实现堆 在写堆之前我们先来想一下如果我们要在堆中插入数据该怎么办
因为我是用数组实现所以在插入时是需要考虑扩容的
插入之后还要保证大堆还是大堆小堆还是小堆 我们再次插入一个60的话就需要和他的祖先进行交换了我们通过下标计算出60的父亲是25然后交换60和25接着再次重复进行上面的步骤交换60和56这次才又变成了大堆
上面这个过程我们叫做向上调整向上调整最多调整高度次
继续回到我们的堆来我们来写堆的结构
typedef int HPDataType;
typedef struct Heap{HPDataType* a;int size;int capacity;
}HP;
使用size来记录当前存储元素数量capacity记录容量
堆的初始化
void HeapInit(HP* php) {assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php-a NULL) {perror(malloc fail);return;}php-size 0;php-capacity 4;
}我们传的是结构体的指针所以一定不能为空需要进行断言接着我们给堆的数组开辟空间初始大小根据需要来定开辟是否成功我们判断一下接着就是初始化其他元素了
堆的销毁
void HeapDestroy(HP* php) {assert(php);free(php-a);php-size 0;php-capacity 0;free(php);
}
释放数组和空间即可
堆的插入
void HeapPush(HP* php, HPDataType x) {assert(php);if (php-size php-capacity) {HPDataType* tmp realloc(php-a,sizeof(HPDataType) * php-capacity * 2);if (tmp NULL) {perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}
在插入前我们要先判断是否需要扩容接着插入并size即可但是我们上面说了在插入后要保证堆还是堆我们需要向上调整所以我们这里写出向上调整算法
向上调整算法
void Swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}
void AdjustUp(HPDataType* a,int child) {int parent (child - 1) / 2;while (child 0) {if (a[child] a[parent]) {Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else {break;}}
}
我们根据上面讲的例子就可以明白这是一个循环我们先找到父节点接着进入循环循环结束条件为child0即插入的元素走到堆顶循环里我们对孩子和父亲进行比较若父亲比孩子小我们交换二者接着让下标移动否则退出循环
有了插入我们对我们的堆进行一下测试 我们通过调试来看堆里的数据发现为645312这就是我们的大堆没有问题
堆的删除
堆的删除是删除堆里的一个元素在写删除之前我们仔细想想我们是删除堆的哪里呢
是头还是尾删尾非常轻松但是删尾没有意义所以堆的删除是删除头也叫删除堆顶
堆顶是一个堆里最大最小的数据在实际中无论是堆排序还是topK都是选大小所以我们需要选出最值
那我们删除堆顶后应该怎么办呢举个例子【401015123】这是一个堆当我们把40删除后我们是要把后续的数据向前挪动一位吗答案是错误的 挪动删除有两大问题1.效率低下2.父子兄弟关系全乱了
原来10和15是兄弟现在10变成了15的父亲而且此时还不是大堆
我们要将堆顶的元素和堆中最后一个元素交换位置 交换到末尾后删除就简单了而且我们此时再单看左子树和右子树也都符合我们的要求都是大堆只有堆顶不满足此时就需要一个向下调整算法
void HeapPop(HP* php) {assert(php); assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a,php-size,0);
}
我们先看删除函数我们交换堆顶与堆最后一个元素的位置使size-1即可接着就是向下调整
向下调整算法
void AdjustDown(HPDataType* a,int n, int parent) {int child parent * 2 1;while (child n) {if (child1n a[child] a[child 1]) {child;}if (a[child] a[parent]) {Swap(a[child], a[parent]);parentchild;child parent * 2 1;}else {break;}}
}
与向上调整类似也是一个循环只不过这次我们是从头开始调整的所以需要多一个参数来接收数组大小向下调整是将堆顶这个小的数据放在他应该出现的位置但和向上调整不同父节点有两个孩子我们选择和较大的孩子进行交换不然可能会出现一些别的情况我们先假设左孩子大然后进行比较如果这个节点有右孩子并且右孩子更大那么就将child更新然后我们对父亲和孩子进行比较如果孩子比父亲大就交换否则退出循环
向上调整和向下调整都是有前提的向下调整的前提是左右子树都是大堆/小堆向上调整的前提是除了child位置前面的数据构成堆
取堆顶元素
HPDataType HeapTop(HP* php) {assert(php);return php-a[0];
}
判断堆是否为空
bool HeapEmpty(HP* php) {assert(php);return php-size 0;
}
堆中元素个数
int HeapSize(HP* php) {assert(php);return php-size;
}这三个函数都非常简单
有了这些函数我们来对堆进行一下测试 堆排序
有了上面的知识我们接着来学习堆排序刚才的操作只能叫做有序打印而不是排序现在才是真正的排序 堆排序并不是我们写一个堆将数据全部放入堆里然后再取堆顶这样做的话效率太低我们还要写一个堆出来
我们看我们的数组虽然有了数据但这些数据并不能构成堆所以我们需要建堆
我们需要用向上调整来建堆就是模拟插入的过程即我们先把数组第一个元素看作堆里的元素接着把第二个元素看作堆的元素插入然后向上调整接着是第三个元素以此类推 这种建堆的时间复杂度为O(N*logN)此时我们的堆就建好了
通过调试我们可以看到 接着我们要排升序的话要建大堆还是小堆呢
很大人可能会认为排升序要建小堆但是建小堆就出问题了小堆的话第一个数排好了剩下的数怎么办呢就又变成了我们上面的挪动删除那样了
所以我们需要建大堆我们将最大的数和最后一个元素交换位置接着我们不管最后一个数将前面的数看作堆然后向下调整最多调整高度次就可以选出次大的数时间复杂度为O(logN)
堆排序的时间复杂度为O(N*logN)
void HeapSort(int* a,int n) {//建堆向上调整for (int i 1; i n; i) {AdjustUp(a, i);}int end n - 1;while (end0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
堆排序写起来是很简单的前提是有我们的向上调整和向下调整 排降序的话建小堆即可
我们的建堆还有一种办法是使用向下调整建堆这种更常用我们要从倒数第一个非叶子节点开始调整因为调整叶子节点没意义 我们从6这个节点开始向下调整6是尾节点的父亲我们可以通过计算得到调整完6后我们要调整7 6往前走一步就到了7我们找到7这个节点左右孩子大的那个就是9然后交换9和7接着调整5交换8和5以此类推最终9到达了堆顶
向下调整的效率是比向上调整高的并且我们只需要写一个向下调整不需要写向上调整就可以完成堆排序 n-1是最后一个数的下标再-1除以2是求父亲节点 接着我们来对比向上调整和向下调整的效率
向下调整与向上调整效率计算
向上调整建队的时间复杂度为O(N*longN)向下调整为O(N)
下面我们进行证明 我们向下调整是从倒数第二层开始调整假设高度为h倒数第二层节点数为2^(h-2)
我们用T(N)表示建堆的总次数
倒数第二层最坏需要调整1次举个例子 我们的这个堆里倒数第二层里的7需要和最后一层的9进行交换所以是调整1次在最坏的情况下倒数第二层的所有节点都需要和他的孩子进行交换
所以倒数第二层的总调整次数为2^(h-2)*1 倒数第三层总调整次数为2^(h-3)*2
......
第二层总调整次数为2^1*(h-2)
第一层需要调整2^0*(h-1)
T(N)2^(h-2)*12^(h-3)*2......2^1*(h-2)2^0*(h-1)
这是一个等差乘以等比我们要用错位相减法来计算
两边同时乘以2后变成2*T(N)2^(h-1)*12^(h-2)*2......2^2*(h-2)2^1*(h-1)
接着我们进行相减得到T(N)2^(h-1) 2^(h-2)2^(h-3)... 2^22^1 - 2^0*(h-1)
最后的 - 2^0*(h-1)我们化解为 -(2^0-h)原理为2^0是1我们不写就变成了h-11又可以写成2^0
此时T(N)2^(h-1) 2^(h-2)2^(h-3)... 2^22^12^0 -h
前面的是是等比数列计算结果为2^h-1所以T(N)2^h-1-h
如果这棵数有N个节点那么2^h-1NN也就是数组大小所以T(N)的前面是Nh是longN
所以向下调整的时间复杂度为O(N-longNlongN可以忽略不记所以时间复杂度为O(N)
分开看就是每一层的节点数乘以向下调整多少次然后加起来
接着我们看向上调整建堆
T(N)2^1*1 2^2*2 ... 2^(h-2)*(h-2) 2^(h-1)*(h-1)
我们分析一下2^1*1代表第2层节点数乘以调整次数1次第二层有两个节点我们是模拟插入即先插入一个这个节点有可能和第一层的节点进行交换接着插入第二个第二个节点也可能和第一层的节点交换交换次数最多为1其他的以此类推
接着我们再用错位相减法计算
2*T(N)2^2*1 2^3*2 ... 2^(h-2)*(h-3) 2^(h-1)*(h-2) 2^(h)*(h-1)
相减得到T(N) -2^1 - 2^2 -2^3 - ...... -2^(h-2) - 2^(h-1) 2^(h)*(h-1)
2^(h)*(h-1)分解变为 -2^h 2^h*h不分解也可以
最终得到T(N) - 2^h2 2^h*h - 2^h
又N2^h-1T(N)最后左边是N 中间是N*longN右边也是N即时间复杂度为O((longN-2)*N)
也就是N*longN
所以向上调整的效率是比向下调整的效率要低的综上我们的堆排序用向下调整就行
Top-K问题 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆 2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素 我们要找出N个数里最大的前K个我们可以建N个大堆然后pop k次就行
那假设N很大呢比如N为100亿
此时数据在内存存不下数据是在磁盘文件里的要解决这个问题就有人想出了这样的一个方法
我们前k个数据建小堆遍历剩下的数据如果这个数据比堆顶数据要大就替代他进堆向下调整最后这个小堆的数据就是最大的前k个
这个思想是不是非常巧妙最大的前k个来了一定比堆顶大就可以进堆如果我们建大堆的话就有可能有一个很大的数在堆顶其他数就进不了堆了
void PrintTopK(const char* file, int k) {//1.用前k个元素建小堆int* topk (int*)malloc(sizeof(int) * k);if (topk NULL) {perror(malloc fail);return;}FILE* fout fopen(file, r);if (fout NULL) {perror(fopen error);return;}//读前k个数据建堆for(int i0;ik;i){fscanf(fout, %d, topk[i]);}for (int i (k - 1-1)/2; i 0; i--) {AdjustDown(topk, k, i);}//2.将剩下的n-k个元素依次与堆顶元素比较满足条件进行替换int val 0;int ret fscanf(fout, %d, topk[i]);while (ret ! EOF) {if (val topk[0]) {topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(fout, %d, val);}//打印数据for (int i 0; i k; i) {printf(%d , topk[i]);}printf(\n);free(topk);fclose(fout);
}
假设数据在文件里所以我们使用文件的方式来写这个函数最后的打印数据大家根据需求来修改即可
以上即为本期全部内容希望大家可以有所收获
最后附上全部代码
全部代码
//heap.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int HPDataType;
typedef struct Heap{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapPush(HP* php,HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void HeapDestroy(HP* php);
//heap.c
#includeheap.h
void HeapInit(HP* php) {assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php-a NULL) {perror(malloc fail);return;}php-size 0;php-capacity 4;
}void Swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}
void AdjustUp(HPDataType* a,int child) {int parent (child - 1) / 2;while (child 0) {if (a[child] a[parent]) {Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else {break;}}
}void HeapPush(HP* php, HPDataType x) {assert(php);if (php-size php-capacity) {HPDataType* tmp realloc(php-a,sizeof(HPDataType) * php-capacity * 2);if (tmp NULL) {perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}void AdjustDown(HPDataType* a,int n, int parent) {int child parent * 2 1;while (child n) {if (child1n a[child] a[child 1]) {child;}if (a[child] a[parent]) {Swap(a[child], a[parent]);parentchild;child parent * 2 1;}else {break;}}
}void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a,php-size,0);
}HPDataType HeapTop(HP* php) {assert(php);return php-a[0];
}
bool HeapEmpty(HP* php) {assert(php);return php-size 0;
}
int HeapSize(HP* php) {assert(php);return php-size;
}void HeapDestroy(HP* php) {assert(php);free(php-a);php-size 0;php-capacity 0;free(php);
}
//test.c
#includeheap.h
void AdjustUp(HPDataType* a, int child);
void Swap(int* x, int* y);
void AdjustDown(HPDataType* a, int n, int parent);
void test1() {HP hp;HeapInit(hp);HeapPush(hp, 1);HeapPush(hp, 2);HeapPush(hp, 3);HeapPush(hp, 4);HeapPush(hp, 5);HeapPush(hp, 6);while (!HeapEmpty(hp)) {printf(%d , HeapTop(hp));HeapPop(hp);}
}void HeapSort(int* a,int n) {//建堆向上调整/*for (int i 1; i n; i) {AdjustUp(a, i);}*///向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(a, n, i);}int end n - 1;while (end0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}void PrintTopK(const char* file, int k) {//1.用前k个元素建小堆int* topk (int*)malloc(sizeof(int) * k);if (topk NULL) {perror(malloc fail);return;}FILE* fout fopen(file, r);if (fout NULL) {perror(fopen error);return;}//读前k个数据建堆for(int i0;ik;i){fscanf(fout, %d, topk[i]);}for (int i (k - 1-1)/2; i 0; i--) {AdjustDown(topk, k, i);}//2.将剩下的n-k个元素依次与堆顶元素比较满足条件进行替换int val 0;int ret fscanf(fout, %d, topk[i]);while (ret ! EOF) {if (val topk[0]) {topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(fout, %d, val);}//打印数据for (int i 0; i k; i) {printf(%d , topk[i]);}printf(\n);free(topk);fclose(fout);
}void test2() {int a[10] { 2,1,5,7,6,8,0,9,4,3 };HeapSort(a, 10);for (int i 0; i 10; i) {printf(%d , a[i]);}
}
int main() {test2();return 0;
}
如有错误还请指正
