当前位置：首页 > article >正文

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

article 2024/9/30 6:58:08

堆排序

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(n*\log_{2}N)$

排升序建大堆示意

![[Pasted image 20240927155920.png]]

交换a0和a5
从堆顶开始向下调整，直到称为大顶堆

![[Pasted image 20240927160225.png]]

交换a0与a4
继续调整为大堆
交换a0与a3
继续调整为大堆
交换a0与a2
交换a0与a1
完成
这样最终数组就是升序的

堆排序是一种选择排序

排降序建小堆

//升序
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]]

第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}+\dots+2^{h-1}+2^{h})+2^{h}\cdot h$
$T(h)=-(2^{0}+2^{1}+2^{2}+\dots+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)$

向下调整建堆

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

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

![[Pasted image 20240927164044.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]]

往前遍历，将小标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}\cdot2+\dots+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

读取文件中的前100个数据，在内存数组中建立一个小堆
再依次读取剩下的数据，跟堆顶数据比较，大于堆顶，就替换他进堆，向下调整
所有数据读完，堆里面的数据就是最大的前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，在文件里随机添加几个超过一百万的数，看是否出现在程序结果里，如果把这些随机插进去的数都能找到，就代表程序是正确的

查看全文

http://www.kler.cn/news/322822.html