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

堆的应用——堆排序和TOP-K问题

article 2025/1/16 21:06:18

1.堆排序

想法⼀：

基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构（之前的文章有讲解），去实现排序。

void HeapSort(int* a, int n)
 {
 HP hp;
 for(int i = 0; i < n; i++)
 {
 HPPush(&hp,a[i]);
 }
 int i = 0;
 while (!HPEmpty(&hp))
 {
 a[i++] = HPTop(&hp);
 HPPop(&hp);
 }
 HPDestroy(&hp);

先依次入堆，然后再将堆顶，数据依次取出，为大堆即是降序，小堆为升序。实际上这种方法使用起来是很不方便的，必须要有堆的数据结构，而且时间复杂度为O（n）。

想法⼆：

数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据。

void HeapSort(int* arr, int n)
{
	//根据给定的arr来进行建堆
	//child:n-1  parent:(n-1-1)/2
	向下调整算法建堆
	//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)
	//{
	//	AdjustDown(arr, i, n);//O(logn)
	//}
	
	//向上调整建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}

	//堆排序
	//排升序---建大堆
	//排降序---建小堆
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
	

}

这里利用的是堆的思想，而不是直接用堆来排序，首先要建堆，将传进来的数组入堆，这里以建小堆为例，利用向下调整的方法，将一个个依次调整直到，直到根节点；

这里完成了建堆，那后面接下来，排序怎么办，其实利用思想将堆顶元素，与最后一个元素交换，再将元素个数减一，将剩余的堆进行调整，依次交换直到到堆顶。最后发现建的小堆，其实是降序排列，反之降序是建小堆。

这样就排序完成。

注意：这里考虑一个问题，向上调整可以建堆，向下调整也可以建堆，那个时间复杂度更低。

1.2向上调整算法和向下调整算法比较：

向上调整算法：

往下结点个数逐渐增多，向下调整次数增多；

可以推出向上调整建堆时间的复杂度：O(n*logn)；

向下调整算法：

可以推出向下调整建堆时间的复杂度：O（n）；

比较发现向下调整算法更优。

2.TOP-K问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：

第一步：⽤数据集合中前K个元素来建堆

（这和前面堆排序有一些相似）

前k个最⼤的元素，则建⼩堆；

前k个最小的元素，则建⼤堆；

第二步：⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素

将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素

void TopK()
{

	int k = 0;
	printf("请输入K：");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		exit(1);
	}
	//找最大的前K个数，建小堆
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}
	//读取文件中前K个数据建堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数据，跟堆顶比较，谁大谁入堆
	//调整堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);
}

这里一些文件操作函数，可以看看小编前面的文章有讲解。

查看全文

http://www.kler.cn/a/371006.html