【数据结构篇】探索堆的算法的巧妙

须知 

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

接上篇：【初阶数据结构】实现顺序结构二叉树-＞堆（附源码）-CSDN博客 

上篇文章我们提及两个算法：向上调整算法和向下调整算法

哪个算法更高效？

1.向上调整算法时间复杂度

示例代码：

void AdjustUp(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->size == php->capacity)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	
	AdjustUp(php->arr, php->size);

	++php->size;
}

因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本

来看的就是近似值，多⼏个结点不影响最终结果)

1.1 分析：

 注：时间复杂度计算最坏情况下的次数,最差的情况就是堆中每个节点都要移动尽可能多的步数，可以得到下面计算公式：

则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

上述使用错位相减求和。

向上调整算法建堆时间复杂度为： O ( n ∗ log 2 n )  即 O(nlogn)

 2. 向下调整算法时间复杂度

堆的删除

删除堆是删除堆顶的数据，将 堆顶的数据根最后⼀个数据⼀换 ，然后删除数组最后⼀个数据，再进⾏向下调整算法。

步骤（如下图）：

示例代码：

void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	while (child < n)
	{
		//找左右孩子中找最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

注意：向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

向下调整算法

• 将堆顶元素与堆中最后⼀个元素进⾏交换

• 删除堆中最后⼀个元素

• 将堆顶元素向下调整到满⾜堆特性为⽌

2.1 分析： 

3. 堆的应用

优先级队列的使用场景：包括定时任务轮训问题、合并有序小文件

求Top K值问题【使用一个堆解决】求中位数、百分位数

大数据量日志统计搜索排行榜

3.1 堆排序

堆排序是一种利用堆这种数据结构设计的排序算法

3.1.1 排序一 

使用现成数据结构->堆，将数据如堆，再取堆顶元素，在删除堆顶数据

// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort1(int* a, int n)
{
 	HP hp;
    int arr1[6] = { 34,29,48,23,10,50 };
 	for(int i = 0; i < 6; i++)
	{
 		HPPush(&hp,a[i]);
 	}
     int i = 0;
     while (!HPEmpty(&hp))
     {
    	 a[i++] = HPTop(&hp);
     	HPPop(&hp);
     }
      HPDestroy(&hp);
 }

使用麻烦，同时代码量还多，效率低，不建议使用。

3.1.2 排序二

比如排升序：建大堆，为啥？

依次将堆顶最大的数据与最后一个（不断发生变化）元素交换，每次都是将最大的数据放最后，可以想象一下，就是升序了。

// 升序，建⼤堆
// 降序，建⼩堆
// O(N*logN)
void HeapSort2(int* arr, int n)
{
	int i = 0;
	for ( i = 0; i < n; i++)
	{
		HPAdjustUp(arr, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&arr[0],&arr[end]);
		HPAdjustDown(arr, 0, end);
		end--;
	}
}

时间复杂度：O（nlogn）

3.1.3 排序三

void HeapSort3(int* arr, int n)
{
	for (int i =(n-1-1)/2 ; i >= 0; i--)
	{
		HPAdjustDown(arr, i, n);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		HPAdjustDown(arr, 0, end);
		end--;
	}
}

建议使用向下调整算法建堆，原因：

移动多的步数节点少，移动少的步数节点多。

而向上调整算法：移动少的步数节点多，移动多的步数节点少。

显然少的步数少，次数就更少。

3.2 Top-k问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。

⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。

最佳的⽅式就是⽤堆来解决，基本思路如下：

⽤数据集合中前k个元素来建堆
前k个最⼤的元素，则建⼩堆；前k个最⼩的元素，则建⼤堆
⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素 ，然后再将交换进去后的元素向下调整（保证这k个元素始终是堆），最后将剩余N-k个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前k个最⼩或者最⼤的元素
代码如下:

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()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	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]);
	}

	//建堆---小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		HPAdjustDown(minHeap, i, k);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		//读取到的数据跟堆顶的数据进行比较
		//比堆顶值大，交换入堆
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			HPAdjustDown(minHeap, 0, k);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}

	fclose(fout);
}

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

相信通过这篇文章你对堆排序的有了初步的了解。如果此篇文章对你学习数据结构有帮助，期待你的三连，你的支持就是我创作的动力！！！