【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树（二）（内含TOP-K问题）

埋头编程

发布于 2024-10-16 18:53:16

530

发布于 2024-10-16 18:53:16

文章被收录于专栏：C/C++

前言

在我们学习完树和二叉树的一些基本概念和性质之后，我只是简单的讲解了一下树的创建方式，我们还并未讲二叉树的一些应用。那么在本文中我就会讲二叉树的应用——“堆”，以及用对这个数据结构来实现堆数组进行排序的功能。这个就是大名鼎鼎的"堆排序"。

我还会针对堆排序给大家再次拓展一个大家在以后编程的道路上，会经常的遇到的一个实际问题：就是在一大堆数据中找出最大或最小的前几个数，这个问题的本质就是堆排序，我们也将这种问题，称为"TOP-K"问题。至于它是怎么实现的，请大家接着往下看！

1. 堆

1.1 堆的概念

我在这里不想给大家讲官方的定义，就直接给大家以一种更好理解的讲解。

堆，其实就是一棵完全二叉树。但是这棵完全二叉树得满足一些性质，

性质1：堆中某个结点的总是不大于或不小于其父节点的值；
性质2：堆总是一颗完全二叉树。(这个我们提到过了)

所以我们就记住以上两个性质，如果都符合了，那你就可以说这是"堆"。

由性质1就可以引出"堆"的两种类型。

1.2 堆的分类

堆分为两种：

大堆（大根堆）：首先它得是一棵完全二叉树，其次它的某一个节点都不大于其父节点(小于或等于其父节点)。这个就是大堆的玩法。
小堆（小根堆）：首先它得是一棵完全二叉树，其次它的某一个节点都不小于其父节点(大于或等于其父节点)。这个就是小堆的玩法。

还记得吗？完全二叉树可以使用顺序表来实现，这个是得益于完全二叉树的特性决定的。既然堆也是一棵完全二叉树，那么我们也就可以用类似于顺序表这种物理结构(顺序存储)来进行堆的实现。

在这里，先给大家一幅图，感受大堆和小堆在逻辑结构和物理结构的模样，帮助大家更好的理解堆这个数据结构:

2. 堆的实现

讲完堆的基本概念之后，我就要详细的给大家讲讲堆是怎样用代码实现的，内容很丰富，希望大家能够好好看！

2.1 堆的结构体设置

我们在之前讲过了，堆是一棵完全二叉树，我们可以用顺序表来实现。那我们就可以这样定义堆的结构体：

//对int进行起别名，是为方便代码的后期维护
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a;
	int size; //记录申请动态空间中有效的数据个数
	int capacity; //记录空间大小
}Heap;

2.2 堆的初始化

我们在开始实现每一个数据结构的各接口操作之前，我们都得为这个数据结构进行初始化，这些都是一些老套路了。

void HeapInit(Heap* php)
{
	assert(php); //传进来的指针不能是空指针，不要就会造成对空指针进行解引用的误操作
	php->a = (HeapDataType*)malloc(sizeof(HeapDataType)*4);
	php->size = 0;
	php->capacity = 4; //因为我申请了4个HeapDataType类型大小的空间
}

2.3 堆的销毁

有动态内存申请，就必要要释放空间，我们不能总是让操作系统来帮我们擦屁股，我们得有意识的释放动态内存申请之后的空间，这对于我们提升代码的能力是一种很好的帮助。

void HeapDestory(Heap* php)
{
	assert(php);
	
	free(php->arr);
	php->arr = NULL;//养成好习惯
	
	php->size = 0;
	php->capacity = 0;
}

2.4 添加数据到堆

这里我们只需要一个函数就行。

那这时有的读者就会提问了，为什么不写一个头插数据的函数和一个尾插数据的函数，而只需要写一个添加数据的函数即可？

原因就是，我们在之前反复提到，堆是一棵特别的完全二叉树。那我们往这个堆中添加数据，添加完数据之后，这个数据结构也还是堆啊。那既然是堆，就得满足堆的特性。我们总不能把人家的东西给彻底玩坏了吧。
那不管是头插还是尾插，甚至是在某个位置上插入数据，在最后都得被调整到符合堆这个数据结构特点的位置上。这就会给我们一个感觉就是不论我在哪个位置上插入，跟我直接插入数据效果是一样的。为此我们直接洗一个插入数据的函数即可。

上面的解释中，提到了一个名词"调整"，那到底怎样调整呢？这个就是本文的核心所在，怎么解决调整数据的问题。

2.4.1 "向上调整"算法

在讲如何调整数据使之再次成为堆之前，我要给大家灌输一个思想，这个思想也是很多人在刚开始学习堆时，比较难以转换的。这个思想就是“看树不是树”。

什么意思呢？

堆在逻辑上是一棵完全二叉树，但是在物理结构上是顺序表。所以我们要想堆不过就是在内存中连续存储的数组罢了。

那基于这层思想，我们向堆里面插入数据，无非就是往数组中插入一个数据。插入完数据之后，再进行数字位置之间的调整，使这个数组再次成为堆。这个就是本算法的核心思想。

那我们该如何调整数组中数字的位置，使之成为堆呢？ 在开始讲之前，我会结合以下的这棵完全二叉树进行讲解（这里我拿大堆举例）

可以看到它物理结构时候的样子，那我们先插入一个数字看看改变之后的样子。

可以看到的一个规律就是，我即使添加了一个数据之后，仍有部分的子树仍然是遵循堆的玩法的。这就给我们提供了一个很重要的思考方向，就是从把"堆"弄的不像"堆"的的那棵子树入手。可以从上面的图中看出，“罪魁祸首”的那棵树在我们添加数据的那个节点直至它的祖先，形成的类似于"导线"的样子。

讲了这么多，就是让大家明白一个道理。为什么这个算法叫做"向上调整"？是由它的操作决定的。则会个算法通过将添加的数据的不断地往上调整，最终到达属于它的"皇位"之上。

那接下来，我就得聊一聊怎么挪动的了。这里针对的是大堆。

可以看到的是挪动之前，我们得先判断它是否需要挪动？挪动到什么位置就停止？这个就必须要知道孩子节点与其父节点之间的值的大小关系了。

现在我告诉大家一个公式，这个公式十分重要，大家一定要理解性记忆！！！

假设孩子结点叫做child，父亲节点叫做parent。(这里的 child 和 parent 的值是数组的下标) parent = (child - 1) / 2 left_child = parent * 2 + 1 right_child = parent * 2 + 2 倘若我们真的掌握了这三条公式，我们就可以通过孩子结点的下标直接找到其父节点，我们也可以根据父节点找到其对应的孩子节点。这两者可以相互被访问！

ok，有了以上的思路，我们就开始写代码吧。

void HeapPush(Heap* php, HeapDataType x)
{
	if(php->size == php->capacity)
	{
		HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType) * 2 * phph->capacity);
		if(tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//成功扩容
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[size] = x;
	php->size++;
	
	//对插入的数据进行位置调整，使之再次成为大堆！得用到向上调整算法
	AdjustUp(php->a,php->size);
}

void Swap(HeapDataType* x, HeapDataType* y)
{
	HeapDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HeapDataType* a,int child)
{
	int parent = (child - 1) / 2;
	while(child > 0)
	{
		if(a[child] > a[parent]) //将这个大于号改为小于号就会变为小堆排序，但前提是这个堆在修改之前是个小堆。
		{
			//就得交换孩子结点和父亲节点的值
			Swap(&a[child],&a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			//只要遇到父节点大于孩子节点的值就直接跳出循环，原因是之前这个本来就已经是个堆了
			break;
		}
	}
}

ok，我们代码就这样水灵灵的写出来了。那么我请大家思考一个问题，我把while循环的额条件变为parent>=0可以吗？

也许有的人会说，这个好像可以吧。但事实上，我不建议大家这么写。大家不妨思考一下，当parent变为0时，循环条件成立，进入循环执行循环体。当执行到parent = (child - 1) / 2这条语句时，parent的值是0，为此它还会再一次进入循环。但不会出现死循环的情况，因为if条件已经不满足了。为此这里还是建议大家写child>0这个判断条件。

2.5 从堆中删除数据

讲完了添加数据到堆的操作之后，肯定还要再讲它的孪生兄弟"从堆中删除数据"。

它的思想跟添加数据的思想大部分是一致的，这里我就不再讲多余的部分了。直接进入最核心的部分，我们该在哪个位置删除数据？删除完数据之后，父亲结点和孩子节点的大小关系肯定就会混乱了，那我们该怎么调整？

这些问题，在下面我都会给大家一一讲解！睁大眼睛，不要错过了哦！

首先我们先解决第一个问题，该删除数组上哪个位置上的数据？

有的不假思索的就会说，删除数组中最后一个位置上的数据！但是这样删除数据有意义吗？这个是我们要思考的问题。从逻辑角度上看，好像对整棵树没有什么影响啊。确实没有影响，删除这种位置上的数据是没有任何意义的！既然要玩，我们就玩大的！删掉根节点。这就好比在一个黑帮中，老二觊觎老大的位置，狠不得找个机会做掉老大，总而自己主管整个黑帮。老三肯定也是想把老二做掉，让自己走上更高的位置。这个道理就类似于堆的删除操作背后的含义。

到这里，我们就理解了第一个问题，要删除数据就删除堆中的根节点。

接下来，我们就得解决第二个问题。那就是删除完数据之后，父亲结点和孩子节点的大小关系肯定就会混乱了，那我们该怎么调整？

这个问题就好比，有一天老二真的把老大给做掉了，但是老二肯定得收买黑帮成员里面的人心，支持他做老大。

下面我画一幅图，给大家来一个直观的感受。

这个时候，就要在给大家介绍另一个算法“向下调整”。

2.5.1 “向下调整”算法

事先说明一个重要的点，在使用这个算法之前，必须得确保根节点的左右子树都得是堆。

想要删除根节点的数据，我们可以将根节点数据与数组中最后一个位置上数字交换值，或则是直接覆盖。这里简单一点就直接将最后位置的值赋值给根节点，这就相当于将根节点进行删除了。

那下一步我们就得调整各数字的位置了。用得算法就是“向下调整”。

那该怎么向下调整呢？

首先我们知道了一个条件，根节点的左右子树还是一个堆。那我们只需要将根节点(父节点)与它的左右孩子节点的值作比较，如果比左右孩子结点值大的那个更小的话，那就交换它们的值。如果都比这两孩子结点都大的话，那就不用调整位置了。

根据以上的思路，我们就来写写代码。

void HeapPop(Heap* php)
{
	assert(php && php->size != 0);
	php -> size--;
	
	//向下调整算法
	Adjust(php->arr,php->size,0);
}

void AdjustDown(HeapDataType* a,int n,int parent)
{
	//相比较左右孩子结点的值，选取其中最大的那个
	//这里我使用假设法，先假设左孩子的值大于右孩子的值。这样就可以避免设置多余的变量
	int child = parent * 2 + 1; //这个上面提到过的公式
	while(child < n)
	{
		if(child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}

		//比较完左右孩子大小之后，就要跟父节点进行大小的比较了
		if(a[parent] < a[child])
		{
			//说明得交换值了
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

到这里，向下调整的算法也将讲完了！希望大家能够好好的消化。

之后，一些堆的方法接口的就比较简单了，我就一次性给大家写代码即可。

2.6 堆的其它各种方法接口函数

//判断堆是否为空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0 ? true : false;
}

//计算堆的大小
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

//查看堆的根节点的值
HeapDataType HeapTop(Heap* php)
{
	assert(php && !HeapEmpty(php));
	return php->a[0];
}

好了，到这里，我们就能完整的实现一个堆了。

那接下来，我们就来讲一下"堆排序"！

3. 堆排序

堆排序，顾名思义，就是利用堆这个数据结构对数据进行（升序/降序）排序。

回顾一下我们学过的数据结构，从顺序表到链表、栈、队列以及我们现在学的堆。堆这个数据结构有很强烈的现实意义，因为它能给我们的数据进行排序，而且效率是目前效率最高的（在没有学排序算法之前）。

那么我们如何用堆进行排序呢？我先给大家一个场景，先让大家去想！

void HeapSort(int* a,int n)
{
	//怎么实现？
}

int main()
{
	int a[] = {5,2,3,7,1,9,8,10,6,4};
	//堆排序
	HeapSort(a,10);
}

3.1 堆排序的代码实现

现在我来揭晓答案:

void HeapSort(int* a,int n)
{
	//向上调整的时间复杂度为O(N*logN)
	/*for(int i = 0; i < n; i++)
	{
		AdjustUp(a,i);
	}*/
	//向下调整的效率更高，时间复杂度为O(N)
	for(int i = (n - 1 - 1) / 2; i >= 0 ; i--)
	{
		AdjustDown(a,n,i);
	}
	
	//这一步就是将最大的数字，置换到数组的尾部。最后再进行调整
	for(int end = n - 1; end > 0 ; end--)
	{
		Swap(&a[end],&a[0]);
		AdjustDown(a,end,0);
	}
}

int main()
{
	int a[] = {5,2,3,7,1,9,8,10,6,4};
	//堆排序
	HeapSort(a,10);

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

4. TOP-K问题

4.1 什么叫TOP-K

顾名思义，就是求前K个数值。可能是最大的前K个，也可能是最小的前K个。

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

4.2 TOP-K问题求解的思路

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

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

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

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

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

4.3 TOP-K问题的代码实现

这里我们就用文件操作生成10000个数字，每个数字的范围是在0~999之间。找出这10000个数字最大的前10个打印出来。

void CreatData()
{
	srand((unsigned int)time(NULL));
	FILE* fin = fopen("data.txt","w");
	if(fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	
	for(int i = 1; i<=10000; i++)
	{
		fprintf(fin,"%d\n",rand()%1000);
	}
	fclose(fin);
	fin = NULL;
}

void PrintTopK(const char* filename, int k)
{
	FILE* fout = fopen(filename,"r");
	if(fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* topk = (int*)malloc(sizeof(int) * k);
	for(int i = 0; i < k; i++)
	{
		fscanf(fout,"%d",&topk[i]);
	}

	for(int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk,k,i); //这里如果是要选最大的话，调整为小根堆。反之，调整为大根堆。
	}

	int val = 0;
	int ret = fscanf(fout,"%d",&val);
	while(ret != EOF)
	{
		if(topk[0]<val)
		{
			topk[0] = val;
			AdjustDown(topk,k,0);
		}
		ret = fscanf(fout,"%d",&val);
	}

	//最后打印结果
	while(k)
	{
		printf("%d ",topk[k-1]);
		k--;
	}
	fclose(fout);
	fout = NULL;
	free(a);
	a = NULL;
}

大家为了方便测试，可以在data.txt这个文本文件中，将其中10个值改为都大于1000的，这样的话，测试的结果就显而易见了。

测试结果：