数据结构-堆的实现和应用

用户11367247

发布于 2024-12-24 09:21:02

9200

代码可运行

文章被收录于专栏：CodeCode

运行总次数：0

代码可运行

1.堆的概念

堆的底层是数组，所以堆也是一种特殊的数组。

堆分为大堆和小堆

大堆：父节点不小于子节点
小堆：父节点不大于子节点

2.堆的构建

已经提到堆是一种数组，那么要怎么实现呢。

先以小堆为例，已知父节点不小于子节点，使用数组，数组下标0是根节点，1和2是他的子节点，接着1的子节点是3和4,2的子节点是5和6，这样就可以实现一个堆了。

3.堆的实现

既然是数组，就要有指针，容量大小。

4.堆的功能实现

4.1堆的初始化

4.2堆的销毁

4.3堆的插入

一直到这一步，都是和栈是相同的，因为我们插入数据了，这时我们无法保证这是一个堆，所以此时要进行向上调整。

4.3.1向上调整

因为此时插入是数据再最下面，所以要和上面的进行比较调整。

4.4堆的删除

我们是删除堆的最后一个元素，要怎么删除呢，我们可以将最后一个元素和第一个元素进行交换，然后使堆向下调整即可。

4.4.1向下调整法

4.5取堆顶

5. 向上调整法和向下调整法比较

推导时间复杂度，由于用图来表示有些难度，这里直接用笔写出来

这是向下调整法的推导过程

向下调整建堆的时间复杂度如图

下面是向上调整建堆的时间复杂度推导

总结:向上调整算法建堆是优于向下调整建堆的。

6.堆的应用

6.1TOP-K问题

这种问题通常是在较大的数据样本中取出其中的最值，这时就可以通过堆来完成。

通常这类问题样本较大，排序就不太可取，可以建堆来实现。

6.2TOP-K思路

6.2.1用前n个数据来建堆

求最大的前n个就建小堆

求最小的前n个就建大堆

6.2.2剩下的N-K

用剩下的N-K个数据来和堆顶数据比较，不满足就替换堆顶元素

6.3示例

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void test()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 2);
	HPPush(&hp, 4);
	HPPush(&hp, 1);
	HPPush(&hp, 1); 
	printf("%d", HPTop(&hp));

	
}
void CreateNDate()
{
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (file == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void topk()
{
	int k = 0;
	printf("输入k的值\n");
	scanf("%d", &k);
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");

	int* arr = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &arr[i]);
	}
	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, k);
	}
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{

		if (x > arr[0])
		{
			arr[0] = x;
			AdjustDown(arr, 0, k);
		}
	}
	for (int i = 0; i < k; i++) 
	{
		printf("%d ", arr[i]);
	}

	fclose(fout);
}


int main()
{
	CreateNDate();
	topk();
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除

排序