【数据结构初阶】--二叉树(三)-EW帮帮网

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在前面我们完成了堆这个数据结构的代码实现以及堆排序的思想和实现，那么在堆排序中我们采用了一种向下建堆的思想，但其实我们也是可以向上建堆的。在今天这篇博客中我也会给大家分享这种方法，再就是一个经典的TOP-K问题，我们来一起解决一下。

一.向上调整算法建堆和向下调整算法建堆的时间复杂度计算

二.向上调整算法建堆和向下调整算法建堆的时间复杂度对比以及堆排序的时间复杂度

一.向上调整算法建堆和向下调整算法建堆的时间复杂度计算

首先我们先来看一下向上调整算法建堆的代码吧：(向下调整的在上篇博客中有这里就不演示了)

//向上调整算法建堆
for (int i = 0; i < n; i++)
{
	AdjustUp(arr, i);
}

--其本质就是从第一个节点开始，依次向下使用向上调整算法将当前的结构调整成一个堆。

既然向上调整算法和向下调整算法都可以建堆，那是不是他们的时间复杂度都是一样的呢？

-------------先说结论，不是的。

--我们来看一下向上调整算法和向下调整算法的时间复杂度

如图所示我们可知向上调整算法和向下调整算法的时间复杂度都是O(logn)

--那使用它们两个建堆的时间复杂度也相同吗，我们也来一起看看

向上调整算法建堆：O(n*logn)--证明过程如下图

向下调整算法建堆：O(n)--证明过程如下图

--通过计算我们会发现，使用向下调整算法建堆要比使用向下调整算法建堆更优

二.向上调整算法建堆和向下调整算法建堆的时间复杂度对比以及堆排序的时间复杂度

--那为什么向上调整算法和向下调整算法时间复杂度一样，但是他们建堆的时间复杂度会有区别呢？

我们从图中可以看出,建堆的复杂度由节点调整次数和节点个数决定，向上调整算法建堆越往下节点个数越多，调整次数也越多，自然时间复杂度是没有向下调整算法低的。

堆排序的时间复杂度： O(n*logn)

--堆排序的时间复杂度为n*logn，这个时间复杂度算是比较优秀的一种排序算法了。

三.Top-k问题

Top-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名，世界500强，富豪榜，游戏前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据不能一下全部加载到内存中)。最佳的方式就是用堆来解决。

具体思考和解决过程如下图所示：

基本思路：

1.用数据集合中前K个元素来建堆：

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

2.用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素：

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

代码演示： (找前k个最大的，建小堆)

--先给大家回顾一下向上调整算法和向下调整算法处理小堆的实现代码

//向上调整
void AdjustUp(int* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//大堆：>
		//小堆：<
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//向下调整
void AdjustDown(int* arr, int parent, int n)
{
	assert(arr);
	int child = 2 * parent + 1;
	while (child < n)
	{
		//child+1也小于n
		//后面的小堆就是取小的，大堆取大的孩子
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		//大堆：>   小堆：<
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}

主要代码：

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(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() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void topk()
{
	printf("请输入k:");
	int k=0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fout fail!");
		exit(1);
	}

	//申请空间大小为k的空间
	int* MinHeap = (int*)malloc(k * sizeof(int));
	if (MinHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}

	//读取前k个数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &MinHeap[i]);
	}

	//数组调整建堆--向下调整建堆
	//找最大的前K个数，建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(MinHeap, i, k);
	}

	//遍历剩下的n-k个数，跟堆顶比较，谁大谁入堆
	int data = 0;
	while (fscanf(fout, "%d", &data) != EOF)
	{
		if (data > MinHeap[0])
		{
			MinHeap[0] = data;//换了之后记得向下调整回小堆
			AdjustDown(MinHeap, 0, k);
		}
	}
	//打印堆里的数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", MinHeap[i]);
	}
	printf("\n");

	fclose(fout);
}

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