【数据结构】堆排序与TopK问题

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》

🌝每一个不曾起舞的日子，都是对生命的辜负

---

目录

前言

 1.堆的概念和结构

2.堆的实现

2.1向上调整算法

2.2向下调整算法

2.3堆的创建

2.4建堆时间复杂度

2.5堆的插入

2.6堆的删除

2.7堆的代码实现

3.堆的应用

3.1堆排序

3.2TopK问题

---

前言

本篇文章博主主要围绕堆这一数据结构展开，内容包括两种建堆方式，两种建堆方式的时间复杂度分析，最后引入堆的应用：堆排序和TopK问题，希望大家多多点赞收藏支持🔥

---

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码：🌟fanfei_c的仓库🌟

=========================================================================

---

 1.堆的概念和结构

堆的逻辑结构是完全二叉树。

逻辑结构的视角观察：

在大根堆中，双亲节点大于孩子节点；

在小根堆中，双亲节点小于孩子节点。

堆的存储结构是一维数组。 

存储结构的视角观察（设数组K）：

在小根堆中：K[i]<=K[2*i+1] && K[i]<=K[2*i+2]；

在大根堆中：K[i]>=K[2*i+1] && K[i]>=K[2*i+2]；

---

2.堆的实现

2.1向上调整算法

向上调整算法的前提是祖先是堆。

以小堆为例：

1.给定向上调整的起点（孩子节点下标），根据起点下标计算双亲节点下标。

孩子节点与双亲结点间的下标关系：

child=parent*2+1 || child=parent*2+2;

parent=(child-1)/2;

2.比较孩子节点与双亲节点数值大小，若孩子节点小于双亲节点，则交换两者，并将孩子节点的下标更新为之前的双亲节点下标，根据最新的孩子节点下标重新计算双亲节点下标，重复这一过程直到孩子节点为根节点。

代码实现： 

//向上调整
void Adjustup(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;
 
	while (child > 0)
	{
		if (a[child] < a[parent])//建小堆
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

---

2.2向下调整算法

向下调整算法的前提是左右子树是堆。

以小堆为例：

1.给定向下调整的起点（双亲节点下标）和节点总数，根据起点下标计算孩子节点下标。

注意：向下调整时，若有两个孩子节点，则需要确保调整的是较小的孩子节点。

2.比较孩子节点与双亲节点数值大小，若孩子节点小于双亲节点，则交换两者，并将双亲节点的下标更新为之前的孩子节点下标，根据最新的双亲节点下标重新计算孩子节点下标，重复这一过程直到孩子节点超出节点总数。

代码实现：

//向下调整
void Adjustdown(HPDataType* a, int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+11] < a[child])//建小堆
		{
			child = child + 1;
		}
		if (a[child] < a[parent])//建小堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

---

2.3堆的创建

堆的创建既可以使用向上调整算法，也可以使用向下调整算法。

1.向上调整算法建堆

由于向上调整算法的前提是祖先是堆，所以我们需要从第二个节点开始向上调整（即根节点的下一个）。

代码实现：

for(int i = 1; i < n; i++)
{
    Adjustup(a,i);
}

---

2.向下调整算法建堆

 由于向下调整算法的前提是左右子树是堆，所以我们需要从倒数第一个非叶子节点向下调整。

已知节点总数为n，那么倒数第一个节点的下标即为n-1，该节点的双亲节点下标即为(n-1-1)/2，该双亲节点就是倒数第一个非叶子节点（因为堆是完全二叉树）。

代码实现：

for (int i = (n - 2) / 2; i >= 0; i--)
{
	Adjustdown(a,n,i);
}

---

2.4建堆时间复杂度

假设树的高度为h。

1.向上调整建堆时间复杂度

 则需要移动节点总的移动步数为：

即向上调整建堆的时间复杂度为O(N*log₂N)。 

---

2.向下调整建堆时间复杂度

则需要移动节点总的移动步数为：

即向下调整建堆的时间复杂度为O(N)。 

---

2.5堆的插入

首先尾插到该数组，再向上调整即可。

---

2.6堆的删除

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

---

2.7堆的代码实现

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);
 
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	hp->capacity = hp->size = n;
 
	memcpy(hp->a, a, sizeof(HPDataType) * n);
	for (int i = 1; i < n; i++)
	{
		Adjustup(hp->a, i);
	}
}
 
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	assert(hp->a);
	//1.检查容量 
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) *newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
 
	hp->a[hp->size] = x;
	hp->size++;
	
	Adjustup(hp->a, hp->size-1);
}
 
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	--hp->size;
 
	Adjustdown(hp->a, hp->size, 0);
}
 
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	return hp->a[0];
}
 
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
 
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

---

3.堆的应用

3.1堆排序

方法1：

首先，我们当然可以利用已经堆这一数据结构进行输出有序的数据。

以升序为例：

首先构建小堆，然后输出堆顶元素，再Pop，再向下调整，循环执行此步骤直到堆空。

代码实现：

void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		//printf("%d ", HeapTop(&hp));
		a[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

但这样有很明显的缺点：

1.需要堆这样一个数据结构，构建麻烦；

2.空间复杂度的消耗。

---

方法2： 

以升序为例：

首先构建大堆（推荐使用向下调整），此时堆顶元素一定为最大值，然后将堆顶元素与最后一个节点交换，此时最大值就放到了整个数组的最后面，然后除了最后一个值以外，其他的数据再向下调整，调整完成后堆顶元素为次大值，再与数组倒数第二个位置的值交换，这样依此往复就得到了升序数组。

注意：

升序建大堆，降序建小堆。

代码实现：

void HeapSort(int* a, int n)
{
	// 向上调整建堆 （大堆）or  （小堆）
	// O(N*logN)
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
 
	// 向下调整建堆
	// O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

---

3.2TopK问题

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

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

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

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

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

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

 首先可以写一段生成随机数字的程序，并将这些数字写入到文件中。

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

根据上面分析的思路完成代码。

void PrintTopK(const char* filename, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
 
	// 前k个数建小堆
	for (int i = (k-2)/2; i >=0 ; --i)
	{
		AdjustDown(minheap, k, i);
	}
 
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			// 替换你进堆
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
 
	fclose(fout);
}

堆处理大量数据的速度非常快，我们都知道对数的特性，所以堆处理大量数据的能力非常强。在遇到TopK问题或者大量数据排序时，可以考虑使用堆排序。

=========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================