数据结构：堆的应用(堆排序和topk问题)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构：堆的应用(堆排序和topk问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构：堆的应用(堆排序和topk问题),数据结构,数据结构,算法,c语言,开发语言,排序算法

个人主页：个人主页
个人专栏：《数据结构》《C语言》

堆排序

堆排序即是先将数据建堆，再利用堆删除的思想来排序。

将待排序数组建堆
将堆顶数据与数组尾部数据交换
调整新的堆顶数据，使其保证堆的结构不变

重复2,3步直到堆中没有数据结束。

建堆

降序建小堆 (父节点小于等于子节点)
升序建大堆 (父节点大于等于子节点)

建堆有两种思路，向上建堆和向下建堆。其中向下建堆优于向上建堆。

向下建堆：从最后一个子节点的父节点开始向前遍历待排序数组，不断向下调整。
如下：对数组 {16, 72, 31, 94, 53, 23}建小堆
数据结构：堆的应用(堆排序和topk问题),数据结构,数据结构,算法,c语言,开发语言,排序算法
为什么不能从数组首元素开始呢？因为向下调整的前提是根节点的左子树与右子树都是大堆或小堆才可以使用。而空树和只有一个节点的树即可以是大堆或小堆。

堆的删除思想排序

将堆顶数据与未排序数组尾部数据交换
向下调整新的堆顶数据，保证堆的结构不变
将新未排序数组尾部数据与新堆顶数据交换

重复上述步骤，即可完成排序。
也可以解释为什么升序建大堆，降序建小堆。小堆的堆顶数据永远是堆中数据最小的，将堆顶数据与未排序数组尾部交换，重复上述步骤。最小的数据就是数组最后一个元素，第二小的数据就是数字倒数第二个元素… 如此完成了降序。

如下

数据结构：堆的应用(堆排序和topk问题),数据结构,数据结构,算法,c语言,开发语言,排序算法

代码实现

//向下调整 小堆，假设该节点是 i， 右孩子节点是 2 * i + 1，左孩子节点是 2 * i + 2
void AdjustDown(HPDataType* data, int parent, int size)
{
	int child = parent * 2 + 1;

	while (parent < size)
	{
		//防止越界                    找左右孩子中最小的
		if (child + 1 < size && data[child] > data[child + 1])
		{
			child++;
		}

		if (child < size && data[parent] > data[child])
		{
			swap(&data[parent], &data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


// 对数组进行堆排序
//先构建堆    升序：大堆     降序：小堆
//如降序，先建小堆，再将堆顶数据放入数组尾部，从新选择堆顶数据
void HeapSort(int* a, int n)
{
	建堆
	向上建堆   类似于插入数据
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//向下建堆   向下调整的前提：该节点的左右子树要都是大堆或小堆
	//倒着从第一个非叶子结点开始向下建堆
	//             n 是数据个数 n-1 是数组最后一个元素   (子节点 - 1) / 2 == 父节点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}


	//将堆顶数据交换数组尾部数据，再选新的堆顶，再交换新的数组尾
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}

int main()
{
	int arr[] = { 16, 72, 31, 23, 94, 53 };
	int size = sizeof(arr) / sizeof(arr[0]);

	HeapSort(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

top k 问题

top k问题就是从N个数中选出前K个数 (N远大于K)
如下：我们随机创建 10000个小于1000000的数，从中找到5个最大的数

思路

我们可以先以前5个数建小堆，再遍历9995个数，如果该数大于堆顶的数，将该数与堆顶的数替换，再向下调整保证小堆结构，继续遍历剩下的数，直到遍历完9995个数。那么堆中的5个数就是10000中最大的5个数。

代码实现

如何检查代码的正确性？
我们可以先跑一遍造数据的代码，再在其创建的文件中随机改写5个数，使其大于1000000。然后我们就可以屏蔽造数据的函数，来运行PrintTopK函数。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}




//从N个数中选处最大的K个数
//用前K个数建小堆(向下调整 or 向上调整)，遍历N - K 个数，  (如果是大堆，那么有可能堆顶数据在一开始就是 N 个数中最大的)
//如果该数大于堆顶数据，堆顶数据 与 该数 交换在向下调整。
//遍历完 N - K 个数，那么堆中数据就是 N 个数中最大的 K 个数

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//小堆  父节点小于等于子节点
void AdjustDown(int* data, int parent, int size)
{
	int child = parent * 2 + 1;

	while (parent < size)
	{

		if (child + 1 < size && data[child] > data[child + 1])
		{
			child++;
		}

		if (child < size && data[parent] > data[child])
		{
			swap(&data[child], &data[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fin = fopen(file, "r");

	//读取前K个数据
	int* ans = (int*)malloc(sizeof(int) * (k + 1));
	if (ans == NULL)
	{
		perror("malloc:");
		exit(-1);
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &ans[i]);
	}

	//建堆
	for (int i = (k - 1) / 2; i >= 0; i--)
	{
		AdjustDown(ans, i, k);
	}

	while (!feof(fin))
	{	
		//读取数据
		int val = 0;
		fscanf(fin, "%d", &val);

		if (val > ans[0])
		{
			swap(&val, &ans[0]);
			AdjustDown(ans, 0, k);
		}
	}

	
	//打印数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", ans[i]);
	}
	printf("\n");
}


int main()
{
	CreateNDate();

	int k = 0;
	scanf("%d", &k);
	PrintTopK(k);
	return 0;
}