一键网站制作,机关网站建设建议,电子商务能从事什么工作,wordpress页面模板获取内容一、建堆的时间复杂度问题
1、除了向上调整建堆#xff0c;我们还可以向下调整建堆。不能在根上直接开始向下调整。这里的条件就是左右子树必须都是大堆或者小堆。我们可以倒着往前走#xff0c;可以从最后一个叶子开始调整。但是从叶子开始调整没有意义。所以我们可以从倒数…一、建堆的时间复杂度问题
1、除了向上调整建堆我们还可以向下调整建堆。不能在根上直接开始向下调整。这里的条件就是左右子树必须都是大堆或者小堆。我们可以倒着往前走可以从最后一个叶子开始调整。但是从叶子开始调整没有意义。所以我们可以从倒数的第一个的非叶子开始调整。也就是最后一个叶子的父亲节点开始向下调整建堆。一层一层向上进行向下调整建堆把大的数字往上调小的数字往下沉。那么问题来了怎么找到最后一个叶子的父亲节点。
我们先可以求出最后一个孩子的下标然后应用公式 parent child-1/ 2 算出最后一个孩子的父亲节点的下标。 void HeapSort(int* a,int n)
{//首先建立大堆/*for (int i 1; i n; i){UpAdjust(a, i);}*///向下调整建堆的效率要比向上调整建堆的效率要高for (int i (n - 1 - 1) / 2; i 0; i--){DownAdjust(a, i, n);}//交换堆头和堆尾的数字选出最大的数字放到堆尾//然后向下调整int end n - 1;while (end 0){Swap(a[end], a[0]);DownAdjust(a, 0, end);end--;}
}
2、向下调整和向上调整建堆的时间复杂度 向下调整倒数第二层有2^(h-2) 个节点
建堆的调整的次数 错位相减法算出时间复杂度
每层节点个数 × 这一层最坏向下调整多少次 最后的结果为 、
所以时间复杂度为O(N) T(N) N - h。
向上调整 再次使用上面的错位相减法 所以时间复杂度为O(NlogN)。
因为向下调整的过程中节点多的调整的次数少节点少的调整的次数多。向上调整的过程中节点少的调整的次数少节点多的调整的次数多
排序调堆的时间复杂度也是O(NlogN)。 TOPK 问题
1、建N个数的大堆再Pop k次就可以了。
2、加入N很大呢N是100亿呢 K 50 1G大约十亿字节。所以是40G左右
内存中存不下数据是在磁盘文件中。
我们可以用100亿个数中的K个数建立一个小堆。遍历剩下的数据如果这个数据比堆顶的数据大就替代它进堆向下调整最后这个小堆的数据就是最大的前K个。
void HeapTopK(int* a, int n, int k)
{//首先向下调整建堆int* topk (int*)malloc(sizeof(int) * k);//从a数组里读for (int i 0; i k; i){topk[i] a[i];}//建立小堆for (int i (k - 1 - 1) / 2; i 0; i--){DownAdjust(topk, i, k);}//遍历剩下的数如果大于堆顶的数据我们就让它进堆并向下调整for (int i k 1; i n; i){if (a[i] topk[0]){topk[0] a[i];DownAdjust(topk, 0, k);}}
}
