堆排序，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);
}
- 先初始化一个堆
- 将数组中的数据一个一个顺序插入堆里
- 然后将堆顶的数据赋给数组首元素
- 接着删除堆顶，然后读下一个堆顶，再赋给数组的下一位
- 直到整个堆空，数组整个赋了一遍，排序完毕
缺点
-
得先有一个堆的数据结构
-
空间复杂度的消耗
-
建堆
升序：建大堆
降序：建小堆 -
利用堆删除思想来进行排序
向上调整建堆
- 升序建大堆
要排升序，不能建小堆，虽然选出了最小的
建小堆之后，关系全乱了，剩下的数据，不一定是堆
要选次小，只能用剩下的数据重新建堆
升序要建立大堆
把最大的数据选出来以后，把堆顶的数据和最后一个数据交换，最大的数据排好了，在把这个最后的最大的数据不看做堆里的数据，
这样，剩下的数据的相对关系没动，左子树还是大堆，右子树还是大堆，把剩下的数看作堆，向下调整选出次大的，代价是
O
(
log
2
N
)
O(\log_{2}N)
O(log2N)
合计是
O
(
n
∗
log
2
N
)
O(n*\log_{2}N)
O(n∗log2N)
排升序建大堆示意
![![[Pasted image 20240927155920.png]]](https://i-blog.csdnimg.cn/direct/1b7f33e5feed4a0d8f7261e0f8af2c47.png)
-
交换a0和a5
![![[Pasted image 20240927160033.png]]](https://i-blog.csdnimg.cn/direct/d306072f61104934b10c29f359304061.png)
-
从堆顶开始向下调整，直到称为大顶堆
![![[Pasted image 20240927160148.png]]](https://i-blog.csdnimg.cn/direct/d3d61c4b16344735874a35269b001afe.png)
![![[Pasted image 20240927160225.png]]](https://i-blog.csdnimg.cn/direct/1e3e2eb330a944f1bcbc0294aca00d95.png)
-
交换a0与a4
![![[Pasted image 20240927160313.png]]](https://i-blog.csdnimg.cn/direct/4ddca57e74524cd0ace0c685bab3a385.png)
-
继续调整为大堆
![![[Pasted image 20240927160420.png]]](https://i-blog.csdnimg.cn/direct/a7111d537f0a4b73b107fe5052ba9a50.png)
-
交换a0与a3
![![[Pasted image 20240927160457.png]]](https://i-blog.csdnimg.cn/direct/e4d8da0b56f34dab9d38977d65f50b88.png)
-
继续调整为大堆
![![[Pasted image 20240927160543.png]]](https://i-blog.csdnimg.cn/direct/5351ff8aef6a473abdbb83686567d7fd.png)
-
交换a0与a2
![![[Pasted image 20240927160628.png]]](https://i-blog.csdnimg.cn/direct/4e7993cd107242c0b001a27ee7124b44.png)
-
交换a0与a1
![![[Pasted image 20240927160741.png]]](https://i-blog.csdnimg.cn/direct/26b416498b7a4686a1407c9ee233405c.png)
-
完成
这样最终数组就是升序的
堆排序是一种选择排序
- 排降序建小堆
//升序
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从数组尾开始遍历到数组头
时间复杂度
![![[Pasted image 20240927154406.png]]](https://i-blog.csdnimg.cn/direct/6662f2f8f927442da28d2f1278d3b1d5.png)
第1层，
2
0
2^{0}
20个节点，不调整
第2层，
2
1
2^{1}
21个节点，向上调整1次
第3层，
2
2
2^{2}
22个节点，向上调整2次
第4层，
2
3
2^{3}
23个节点，向上调整3次
…
第h-1层，
2
h
−
2
2^{h-2}
2h−2个节点，向上调整h-2次
第h层，
2
h
−
2^{h-}
2h−个节点，向上调整h-1次
Expected node of symbol group type, but got node of type cr
T
(
h
)
=
−
(
2
1
+
2
2
+
⋯
+
2
h
−
1
+
2
h
)
+
2
h
⋅
h
T(h)=-(2^{1}+2^{2}+\dots+2^{h-1}+2^{h})+2^{h}\cdot h
T(h)=−(21+22+⋯+2h−1+2h)+2h⋅h
T
(
h
)
=
−
(
2
0
+
2
1
+
2
2
+
⋯
+
2
h
−
2
+
2
h
−
1
)
+
2
h
⋅
(
h
−
1
)
+
2
0
T(h)=-(2^{0}+2^{1}+2^{2}+\dots+2^{h-2}+2^{h-1})+2^{h}\cdot (h-1)+2^{0}
T(h)=−(20+21+22+⋯+2h−2+2h−1)+2h⋅(h−1)+20
T
(
h
)
=
−
2
h
+
1
+
2
h
⋅
(
h
−
1
)
+
1
T(h)=-2^{h}+1+2^{h}\cdot (h-1)+1
T(h)=−2h+1+2h⋅(h−1)+1
换算到N
T
(
h
)
=
T
(
N
)
=
−
N
+
(
N
+
1
)
⋅
(
log
2
(
N
+
1
)
−
1
)
+
1
T(h)=T(N)=-N+(N+1)\cdot (\log_{2}(N+1)-1)+1
T(h)=T(N)=−N+(N+1)⋅(log2(N+1)−1)+1
T
(
N
)
=
O
(
N
⋅
log
2
N
−
N
)
T(N)=O(N\cdot \log_{2}N-N)
T(N)=O(N⋅log2N−N)
向下调整建堆
建大堆
需要左右子树都是大堆
从下面开始往上调整：
找倒数第一个非叶子节点，也就是最后一个节点的父亲开始调
找到以后，在这个非叶子节点的子树里，进行向下调整
再往前一棵子树走，继续向下调整，
继续往前遍历每一棵子树，直到根节点
![![[Pasted image 20240927164044.png]]](https://i-blog.csdnimg.cn/direct/bc6e6652bd794431b5aba53d7fc6b4a1.png)
- 找到导数第一个非叶子节点，进行向下调整
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为根节点，建大堆，向下调整
![![[Pasted image 20240927164611.png]]](https://i-blog.csdnimg.cn/direct/6c782e3b145640d18b434d2bc88e6117.png)
-
往前遍历，将小标5之前的节点全部作为根节点，向下调整建大根堆
![![[Pasted image 20240927164725.png]]](https://i-blog.csdnimg.cn/direct/d8fc3a6b5c58468ab1bf71145e880925.png)
-
到最后三个节点
![![[Pasted image 20240927164922.png]]](https://i-blog.csdnimg.cn/direct/bd30f8b560a343189d799937ca671d84.png)
-
直到根节点
![![[Pasted image 20240927165015.png]]](https://i-blog.csdnimg.cn/direct/c854e98b9c67419aba4cfd3b2d48f3ab.png)
//升序
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
⋅
2
+
⋯
+
2
1
⋅
(
h
−
2
)
+
2
0
⋅
(
h
−
1
)
T(h)=2^{h-2}+2^{h-3}\cdot2+\dots+2^{1}\cdot(h-2)+2^{0}\cdot(h-1)
T(h)=2h−2+2h−3⋅2+⋯+21⋅(h−2)+20⋅(h−1)
每层的数据个数乘以向下移动的层数
等比每项乘以等差每项
Expected node of symbol group type, but got node of type cr
T
(
h
)
=
2
h
−
1
−
h
T(h)=2^{h}-1-h
T(h)=2h−1−h
T
(
h
)
T(h)
T(h)是向下调整建堆，最坏情况下的合计调整次数
换算关于N的式子，得到时间复杂度
T
(
N
)
=
N
−
log
2
(
N
+
1
)
T(N)=N-\log_{2}(N+1)
T(N)=N−log2(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
- 读取文件中的前100个数据，在内存数组中建立一个小堆
- 再依次读取剩下的数据，跟堆顶数据比较，大于堆顶，就替换他进堆，向下调整
- 所有数据读完，堆里面的数据就是最大的前100个
不能使用大堆，否则最大的数进堆以后，就挡在这里，剩下的数就无法进堆
所以使用小堆，最大的前100个数任意一个数进来都可以进堆
小堆里面，大的数回沉到下面去
时间效率很高，有N个数据
时间复杂度
O
(
N
⋅
log
2
K
)
O(N\cdot \log_{2}K)
O(N⋅log2K)
空间复杂度
O
(
K
)
O(K)
O(K)
如果N远大于K
时间复杂度
O
(
N
)
O(N)
O(N)
空间复杂度
O
(
1
)
O(1)
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，在文件里随机添加几个超过一百万的数，看是否出现在程序结果里，如果把这些随机插进去的数都能找到，就代表程序是正确的