©2020-2024 ioDraw All rights reserved,
Privacy Policy
上次通过数组实现堆排序的时间复杂度为O(NlogN),空间复杂度为O(N)。
优化后时间复杂度O(NlogN),空间复杂度O(1).
考虑优化方案：
1.向下调整建堆。
2.向上调整建堆。
建堆只是为了找到堆中最大或者最小的元素。
1.向上调整建堆
使用向上调整，插入数据的思想建堆。
优化方案本质上就是不开辟新的空间在原数组上进行处理，使其空间复杂度变为O（1）。
void HeapSort2(int* a,int n) { for (int i = 1; i < n; i++) { AdjustUp(a, i); }
for(int i= 0;i<n;i++) printf("%d ", a[i]); printf("\n"); }
现在对其时间复杂度进行计算，为方便计算，采用满二叉树来计算。
以下考虑的是最坏的境况：
第二层： 2^1 个结点 ，向上调整1层；
第三层： 2^2 个结点 ，向上移动2层；
……
第h层：2^(h-1)个结点，向上移动h-1层。
则需要移动的结点的次数：
T (n) = 2^1 * 1+ 2^2*2 +…+ 2^(h-1)*(h-1)
根据数列错位相减法求和公式可知
T(n) = (N+1) * ( log(N+1) - 2 )+2 当n->无穷大 T(n) = NlogN
向上建堆的时间复杂度为O(N*logN).
2.向下调整建堆
前提要求：对必须是大堆或者小堆。
所以要先对数组进行调整。
从倒数第一个非叶子结点开始（最后一个结点的父亲结点）。
因为叶子结点可以单独看作大堆或者小堆。
画图：
调整次数：4次
代码：
void HeapSort3(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i); } for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n"); }
空间复杂度：O（1），时间复杂度O（N）
现证明时间复杂度：
第一层：2^0个结点，需要向下移动h-1层。
第二层：2^1个结点，需要向下移动h-2层。
第三层：2^2个结点，需要向下调整h-3层。
……
第h-1层，2^(h-2)个结点，需要向下移动1层。
所以移动的总次数：
T(n) = 2^0 *(h-1) + 2^1 *(h-2) + …+ 2^(h-2)* 1
根据错位相减法可得出：
T(n) = 2^h - 1 - h
又 n = 2^h - 1
T(n) = n - log(n+1)
当n无穷大时，近似认为T(n) = n
证明完毕。
既然已经有向上建堆和向下建堆两种方法，那么哪种情况更是配建小队，哪种更适合见大堆？？
升序 -- 建大堆
理由：若是升序建小堆最小的数已经在第一个位置了，剩下的关系全都乱了，需要重新建堆，建堆要O(N),再选出次小的，不断建堆选数，如此以时间复杂度O(N)的情况还不如直接遍历轻松。
总之，升序建小堆，效率低，还复杂。
降序--建小堆
那如何建大堆完成排序呢？
建大堆本质上就是尽可能维持堆的稳定。
找到最大的数后，将根位置的数与最后一个数相交换，在n-1组数据中进行向下调整，找到次小的数，将根与第n-1位置的数交换，以此实现升序。
相关代码：
void HeapSort4(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--; } for (int i
= 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }
Top - k 问题
求数据结合中前k个最大元素或者最小的元素，一般情况下数据量都比较大。
Top-k中最简单的方法就是排序，如果数据量非常大，排序就会出现问题（数据不能一次性加载到内存中），但是堆排序可以解决。
1.用数组中前看个元素来建堆。
求最大建小堆，求最小则建大堆。
与升序建大堆，降序建小堆原理相似。
2.用剩余的n-k个元素与对顶的元素作比较，来替换对顶的元素。
记得向下调整。
void TopK(int* a,int n,int k) { //建小堆 int* topk = (int*)malloc(sizeof(int) *
k); assert(topk); for (int i = 0; i < k; i++) { topk[i] = a[i]; } //向下调整建堆 for
(int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(topk, k, i); } for (int j =
k; j < n; j++) { if (topk[0] < a[j]) { topk[0] = a[j]; AdjustDown(topk, k, 0);
} } for (int i = 0; i < k; i++) { printf("%d ", topk[i]); } printf("\n");
free(topk); } int main() { int n = 10000; int* a = (int*)malloc(sizeof(int) *
n); assert(a); srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() %
10000; } a[0] = 100001; a[101] = 100002; a[159] = 123456; a[7459] = 100003;
a[7412] = 100009; a[7826] = 111111; a[7712] = 222222; a[9635] = 999999;
TopK(a,n,8); return 0; }
时间复杂度 O( K+ K*log(N-K) )
空间复杂度：O(K)
当K<<N时，效率也蛮高的。
有不对的地方还请大佬指出。