堆排序，TopK问题|向上调整建堆|向下调整建堆(C)

堆排序

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);
}

• 先初始化一个堆
• 将数组中的数据一个一个顺序插入堆里
• 然后将堆顶的数据赋给数组首元素
• 接着删除堆顶，然后读下一个堆顶，再赋给数组的下一位
• 直到整个堆空，数组整个赋了一遍，排序完毕
  缺点

1. 得先有一个堆的数据结构

2. 空间复杂度的消耗

3. 建堆
   升序：建大堆
   降序：建小堆

4. 利用堆删除思想来进行排序

向上调整建堆

• 升序建大堆
  要排升序，不能建小堆，虽然选出了最小的
  建小堆之后，关系全乱了，剩下的数据，不一定是堆
  要选次小，只能用剩下的数据重新建堆

升序要建立大堆
把最大的数据选出来以后，把堆顶的数据和最后一个数据交换，最大的数据排好了，在把这个最后的最大的数据不看做堆里的数据，
这样，剩下的数据的相对关系没动，左子树还是大堆，右子树还是大堆，把剩下的数看作堆，向下调整选出次大的，代价是$O({\log }_{2}N)$
合计是$O(n\ast {\log }_{2}N)$

排升序建大堆示意

1. 交换a0和a5
   

2. 从堆顶开始向下调整，直到称为大顶堆
   

3. 交换a0与a4
   

4. 继续调整为大堆
   

5. 交换a0与a3
   

6. 继续调整为大堆
   

7. 交换a0与a2
   

8. 交换a0与a1
   

9. 完成
   这样最终数组就是升序的

堆排序是一种选择排序

• 排降序建小堆

//升序
void HeapSort(int* a, int n)
{//建大堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

• 传参传数组的地址和数组大小
• 从数组第一个数开始遍历，每个数都向上调整，这样遍历完之后，这组数据就形成大堆
• 用end指向最后一个元素，也就是最后一个节点
• 将根节点与最后一个节点交换
• 从根节点开始向下调整，直到最后一个节点的最后一个节点
• end–，将最大的一个数从堆中剔除出去
• 然后开始循环，将根节点也就是次大的与当前最后一个节点交换，再向下调整，找出第三大的，再次end–
• 循环直到end从数组尾开始遍历到数组头

时间复杂度

第1层，$2^0$个节点，不调整
第2层，$2^1$个节点，向上调整1次
第3层，$2^2$个节点，向上调整2次
第4层，$2^3$个节点，向上调整3次
…
第h-1层，$2^{h-2}$个节点，向上调整h-2次
第h层，$2^{h-}$个节点，向上调整h-1次
Expected node of symbol group type, but got node of type cr
$$T(h)=-(2^1+2^2+\cdots +2^{h-1}+2^h)+2^h\cdot h$$
$$T(h)=-(2^0+2^1+2^2+\cdots +2^{h-2}+2^{h-1})+2^h\cdot (h-1)+2^0$$
$$T(h)=-2^h+1+2^h\cdot (h-1)+1$$
换算到N
$$T(h)=T(N)=-N+(N+1)\cdot ({\log }_2(N+1)-1)+1$$
$$T(N)=O(N\cdot {\log }_{2}N-N)$$

向下调整建堆

建大堆
需要左右子树都是大堆

从下面开始往上调整：
找倒数第一个非叶子节点，也就是最后一个节点的父亲开始调
找到以后，在这个非叶子节点的子树里，进行向下调整
再往前一棵子树走，继续向下调整，
继续往前遍历每一棵子树，直到根节点

1. 找到导数第一个非叶子节点，进行向下调整

2,3,5,7,4,6,8,65,100,70,32,50,60

设整个数组有n个数据，60的下标就是n-1，这里是12
通过公式计算出它的父节点的下标，13-2除以2等于5也就是6
2. 以6为根节点，建大堆，向下调整

3. 往前遍历，将小标5之前的节点全部作为根节点，向下调整建大根堆
   

4. 到最后三个节点
   

5. 直到根节点
   

//升序
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;}
}

• 传参传数组的地址和数组的大小
• 从倒数第一个非叶子节点开始往前遍历，直到根节点
• 每次遍历把当前节点视为根节点，进行向下调整，循环直到根节点
• 这样从最底层开始，将每棵子树都变为大堆，这样最终从根节点向下调整，整棵树就变为大堆

时间复杂度

用满二叉树来计算
因为最差的情况就是节点最多的时候
总共有h层
最后一层不需要调整，从第h-1层开始调整，每个节点向下调整一次
合计要调整
$$T(h)=2^{h-2}+2^{h-3}\cdot 2+\cdots +2^1\cdot (h-2)+2^0\cdot (h-1)$$
每层的数据个数乘以向下移动的层数
等比每项乘以等差每项
Expected node of symbol group type, but got node of type cr
$$T(h)=2^h-1-h$$
$T(h)$是向下调整建堆，最坏情况下的合计调整次数
换算关于N的式子，得到时间复杂度
$$T(N)=N-{\log }_2(N+1)$$
约等于N

TopK问题

一般情况下，直接建堆，然后popk次

#include "Heap.h"int main()
{int a[] = { 2,3,4,7,4,6,8 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int)){HeapPush(&hp, a[i]);}HeapPrint(&hp);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);return 0;
}

假设10亿个数据，内存存不下，数据在文件中，找出最大的k个
假设k等于100

1. 读取文件中的前100个数据，在内存数组中建立一个小堆
2. 再依次读取剩下的数据，跟堆顶数据比较，大于堆顶，就替换他进堆，向下调整
3. 所有数据读完，堆里面的数据就是最大的前100个

不能使用大堆，否则最大的数进堆以后，就挡在这里，剩下的数就无法进堆
所以使用小堆，最大的前100个数任意一个数进来都可以进堆
小堆里面，大的数回沉到下面去

时间效率很高，有N个数据
时间复杂度$O(N\cdot {\log }_{2}K)$
空间复杂度$O(K)$
如果N远大于K
时间复杂度$O(N)$
空间复杂度$O(1)$

在文件当中找到最大的前k个

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>void PrintTopK(const char* filename, int n, int k)  
{  FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}  int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", %minheap[i]);}//前k个数建小堆for (int i = (k-2)/2; i >= 0; --i){AdjustDown(minheap, k, i);}//将剩余n-k个元素依次与堆顶元素交换，不满则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){//替换进堆minHeap[0] = x;AdjustDown(minHeap, k, 0);}}for (int i = 0; i < k; i++){printf("%d", minHeap[i]);}printf("\n");fclose(fout);
}  void CreateNote()
{int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{//CreateNote();PrintTopK("data.txt", 10);return 0;
}

如何证明程序是对的，找到的是最大的前k个？
前面建立随机数文件的时候mod了个1000000，在文件里随机添加几个超过一百万的数，看是否出现在程序结果里，如果把这些随机插进去的数都能找到，就代表程序是正确的