【数据结构】有关堆你知多少？

目录

​编辑

一. 前言

二. 堆的概念及结构----脆皮烤鸭

        1.堆的概念

        2.堆的结构

三. 堆的操作与实现----剁椒鱼

        3.1 堆的插入与向上调整（以小堆为例）

        3.2 堆的删除与向下调整（以大堆为例）

        3.3 向上调整建堆

        3.4 向下调整建堆

        3.5 向上调整vs向下调整

四. 堆的应用----蒜蓉叫花鸡

        4.1 堆排序

        4.2 TopK算法

五. 堆的其余接口----酸梅汤

        5.1 堆的初始化

        5.2 堆的销毁

        5.3 堆的扩容

        5.4 堆的判空

        5.5 取堆顶元素

        5.6 堆的元素个数

一. 前言

        又到了紧张刺激的理论时间了，今天我们将介绍大家或许耳熟能详的一种结构----堆

        在上期 从树到二叉树 的博客中，我们说到二叉树一般有两种存储结构：顺序存储和链式存储，而我们只详细介绍了链式二叉树的操作及应用。这并不意味着顺序存储完全没有用武之地，而是现实中只有堆才会使用顺序存储，即使用数组来存储。而对于堆这种重要的数据结构，笔者认为只有专门制作一篇博客才能配得上它的高贵身份。因此，本期都是大菜哦，各位可以尽情享受  

         废话少说，上菜！！！

二. 堆的概念及结构----脆皮烤鸭

        1.堆的概念

         在一个有n个元素的序列K = {， ， ，…， }中，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，当满足  且 时，i = 0，1，2…，我们称其为小堆；相对应的，当满足  且 时，i = 0，1，2…，我们称其为大堆。我们将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

        从以上概念中，我们可以提炼出以下三个信息：

•   堆总是一种完全二叉树，其采用顺序存储方式
•   堆中某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值；
•   当序列只有一个元素时，既可以是大堆也可以是小堆

        2.堆的结构

        为什么要采用顺序存储方式？

        由于堆总是一颗完全二叉树，因此数组便成为了用来存储堆的最好方式。数组最大的优点就是支持随机访问，在数组中，只要我们知道其中一个结点的下标，便可以通过完全二叉树父结点和孩子结点的编号关系，快速定位到其父结点或孩子结点。下面列出了小/大根堆的结构及表示：

        由于采用顺序存储，堆结构的代码表示就与顺序表基本一致，如下：

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a; //指向存储堆的数组空间
	int size; //大小
	int capacity; //容量
}Hp;

三. 堆的操作与实现----剁椒鱼

        3.1 堆的插入与向上调整（以小堆为例）

        堆的插入就是将一个元素插入到堆的尾部，如下图所示。

         但是我们可以发现，如果直接这样插入显然是不行的，插入后小堆的结构就被破坏了，所以我们需要对插入后的完全二叉树调整为新的小堆，这里需要用到的就是向上调整算法。

         向上调整算法

         所谓向上调整算法，就是将当前结点从下往上一步步调整直到形成小堆，大致过程如下：

•   可以看到，结点[5]通过两次向上交换移动到了堆顶，此时的树又变为了小根堆。
•   首先我们先比较末尾插入的新结点[5]与其父结点[30]的大小，根据小根堆小的在堆顶，大的    在堆底的特性可知：当父结点比插入结点大时，我们需要进行一次交换以调整堆的结构；而    如果父结点比插入结点小时，说明插入结点并没有破坏小堆的结构，依然符合小堆的特性，    无需进行调整。
•   那么，是不是一次调整后就结束了呢？当然不是。进行一次调整后我们只能保证调整过的那    一部分符合小堆的特性，毕竟只根据新结点父亲结点以及父结点爷爷结点两个条件，我      们并不能保证新结点爷爷结点。如果新结点爷爷结点，则我们进行一次调整后依旧不是      小堆，新结点还需向上调整。由此可以看出，向上调整算法是个不断向上交换调整的算法。
•   算法实现思路：由以上分析，我们需要通过循环控制堆的向上调整。用两个变量parents和      child分别代表父结点和孩子结点的下标，在循环过程中比较父结点和孩子结点的大小，当父    结点孩子结点时，我们就交换父子结点，然后将parents作为新的child，parents改为爷爷      结点的下标，形成迭代用于下次循环比较。
•   循环结束条件：当父结点孩子结点时或者时说明小堆调整完毕，结束循环。
•   注意事项：使用向上调整算法时必须确保原来的树已经是小/大堆，否则无法保证调整后的树    是小/大堆。

        堆的插入代码实现

void Swap(HeapDataType* p1, HeapDataType* p2) //用于交换
{
	HeapDataType tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

static void AdjustUp(Hp* php, int child)  //向上调整算法，child代表孩子结点下标
{
	int parent = (child - 1) / 2; //计算父结点下标，完全二叉树的性质

	while (child > 0) //不推荐使用parent >= 0作为循环条件，会多进行一次循环，并且很别扭
	{
		if (php->a[parent] >  php->a[child])//不满足，向上调整交换
		{
            Swap(&php->a[parent],&php->a[child]);
		}
		else//插入位置满足小堆条件，直接返回
		{
			break;
		}

		//更新下标，迭代
		child = parent;
		parent = (child - 1) / 2;
	}

}

void HeapPush(Hp* php, HeapDataType x) //堆的插入
{
	assert(php);
	CheckCapicity(php); //先检查容量，是否需要扩容
	//插入
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php, php->size - 1);//向上进行调整
}

        3.2 堆的删除与向下调整（以大堆为例）

        有插入就自然有删除。堆的删除是删除堆顶的数据，如下：

        那么问题就来了，堆顶数据删除后，新的堆顶是什么呢？是模仿顺序表一样后续元素全部往前移动吗？如下：

我们发现，如果将后续元素全部前移，原本的孩子可能变为父亲，父亲可能会变成孩子，整个堆的关系就紊乱了，堆的结构就会被完全破坏，需要重新建堆，成本过高。因此我们需要另辟蹊径。

         我们的做法是将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，这样就实现了堆顶数据的删除，并且不会影响堆的结构。如下：

        通过这种方法，我们发现堆顶的左右子树均保持着原先大堆的结构不变，只有交换上来的堆顶元素不满足堆的条件。换句话说，我们只需对堆顶元素的位置进行调整即可 ，调整的方式就是接下来要介绍的向下调整算法

          向下调整算法

         向上调整是从下往上进行调整，那么向下调整就是从上往下进行调整。大致过程如下：

•   经过两次向下调整，堆顶元素[35]来到了合适的位置，此时的树即为大堆
•   我们知道在调整之前除了根结点之外，左右两颗子树均为大堆。根据大堆大的在堆顶，小的    在堆底的特性可知：当堆顶元素比其中一个孩子小时，我们就需要进行交换以调整大堆的结    构；而如果堆顶元素比所有孩子结点小时，说明堆顶元素的位置符合大堆的结构，无需进行    调整。
•   还有最后一个问题：当我们需要进行调整时，堆顶元素要和哪个孩子结点进行交换呢？左        孩子？亦或者是右孩子？很简单，既然是大堆，那我们只要选出较大的孩子进行交换即可（小堆相反），这样就能保证交换后新的堆顶元素一定大于两个孩子结点。
•   与向上调整算法同理，向下调整算法也是要不断向下进行调整，直到不再需要交换。 
•   算法实现思路：因此我们依然通过循环控制堆的向下调整。用两个变量parents和child分别      代表父结点和孩子结点的下标，parents初值为0表示堆顶元素。进入while循环后我们首先需    要比较左右孩子的大小，然后找出较大值与parents进行比较，如果parents大于这个较大        值，则说明此时树已经符合大堆的结构，无需进行调整；如果parents小于这个较大值则向      下进行交换，然后更新parents和child，进行迭代。
•   循环结束条件：当父结点孩子结点较大值或者(元素个数)时说明大堆调整完          毕，结束循环。
•   注意事项：使用向下调整算法时必须确保其左右子树已经是小/大堆，否则无法保证调整后的    树是小/大堆。

        堆的删除代码实现

//交换
void Swap(HeapDataType* p1, HeapDataType* p2) 
{
	HeapDataType tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

//向下调整
void AdjustDown(Hp* php, int parent,int n) //parent为准备向下调整的结点下标，n为元素个数
{
	int child = 2 * parent + 1; //找出左孩子
	while (child < n) //如果child >= n 说明此时parent为叶子结点，无需调整，退出循环
	{
		//在左右孩子中找出较大的孩子
		if (child + 1 < n && php->a[child + 1] > php->a[child])//存在右孩子且右孩子大于左孩子
		{
			child++; //child改为右孩子，表示较大结点下标
		}

		if (php->a[parent] < php->a[child]) //parent小于较大值，需要进行调整
		{
			Swap(&php->a[parent], &php->a[child]); //交换

			parent = child; //更新parent和child，准备下一次循环进行调整
			child = 2 * parent + 1;
		}
		else //parent大于等于较大值，无需进行调整，已经是大堆，退出循环
		{
			break;
		}
	}

}

//堆的删除
void HeapPop(Hp* hp)
{
	assert(hp->size);
	Swap(&hp->a[0], &hp->a[hp->size - 1]); //交换堆顶元素和最后一个元素

	hp->size--; //删除原堆顶元素

	AdjustDown(hp, 0, hp->size); //现堆顶元素向下调整
}

        3.3 向上调整建堆

        Q：给你一个数组如下，要求设计算法将这个数组构建为一个堆。我们该怎么做呢？

int array[] = {27,15,19,18,28,34,14};

        way1：首先我们知道，当数组只有一个元素时，其不仅可以看作大堆也可以看作小堆。那么就有一个很简单的思路，先初始化一个空堆，然后将数组第一个元素放入作为一个堆，然后遍历其他元素往堆的末端插入进行向上调整算法即可。下面是构建小堆过程以及代码：

typedef int HeapDataType;
//堆的初始化
void HeapInit(Hp* php)
{
	assert(php);
	HeapDataType* tmp = (HeapDataType*)malloc(InitSize * sizeof(HeapDataType));
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	else
	{
		php->a = tmp;
		php->capacity = InitSize;
		php->size = 0;
	}
	
}

//堆的创建,向上调整
void HeapUpCreate(Hp* php, HeapDataType* a, int n)
{
	assert(php);
	assert(a);
    HeapInit(php); //初始化堆
	for (int i = 0; i < n; i++)
	{
        //i==0，相当于直接插入a[0]
        //i>0，向堆末端插入a[i]，然后进行向上调整
		HeapPush(php, a[i]); //HeapPush函数的详细代码请见堆的插入
	}
}

int main()
{
	Hp hp;
    HeapDataType array[] = {27,15,19,18,28,34,14};
    HeapUpCreate(&hp,array,sizeof(array)/sizeof(HeapDataType)); //根据array数组创建堆
	HeapDestroy(&hp); //不再使用销毁堆
	return 0;
}

        3.4 向下调整建堆

         除了使用向上调整建堆，我们也可以使用向下调整算法将下面的数组构建为一个堆。实际上，我们会更倾向于使用向下调整算法来建堆，下面我们会通过对比两种算法的时间复杂度进行分析。

int array[] = {27,15,19,18,28,34,14};

        不同于向上调整的是，向下调整不再是边插入边调整，而是直接将整个数组作为一个完全二叉树，然后逐元素进行调整，如下：

        在之前，我们说过使用向下调整算法有一个前提：左右子树必须是个堆。那么我们显然不能从前往后进行调整，因为堆顶的左右子树不是一个堆。为了保证调整某个元素时它的左右子树已经是堆了，我们应该从后往前逐元素进行向下调整。

        那么，第一个需要调整的元素是谁呢？叶子节点没有左右子树，故不需要进行调整，我们应该从第一个非叶子结点开始向下调整调整，即下标为(n-1-1)/2的元素(n为元素个数)。就这样不断调整到根结点即可完成堆的构建。下面是向下调整构建大堆的过程和代码：

//堆的创建，向下调整
void HeapDownCreate(Hp* php, HeapDataType* a, int n)
{
	assert(php);
	assert(a);
	HeapInit(php); //初始化堆

	//将数组的n个元素拷贝到堆中
	if (php->capacity < n)//容量不足先扩容
	{
		HeapDataType* tmp = realloc(php->a, n * sizeof(HeapDataType));
		if (tmp)
			php->a = tmp;
		else
			exit(-1);

		php->capacity = n;
	}
	memcpy(php->a, a, sizeof(HeapDataType) * n);
	php->size = n;

	//从后往前逐元素向下调整建堆
	//n-1 最后一个叶子结点的下标
	//(n-1-1)/2 最后一个叶子结点的父结点下标，即第一个非叶子结点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php, i, n); //向下调整算法，详细代码请见堆的删除
	}
}

int main()
{
	Hp hp;
    HeapDataType array[] = {27,15,19,18,28,34,14};
    HeapDownCreate(&hp,array,sizeof(array)/sizeof(HeapDataType)); //根据array数组创建堆
	HeapDestroy(&hp); //不再使用就销毁堆
	return 0;
}

        3.5 向上调整vs向下调整

         上面我们介绍了两种建堆方法，那么肯定会有许多小伙伴有所疑问：这两种建堆算法在效率上是相差无几还是有所优劣呢？下面我们就来分析分析它们的时间复杂度

         废话少说，直接上图

特别说明：因为堆是完全二叉树，而满二叉树也是完全二叉树，因此上面为了简化使用满二叉树来分析复杂度(时间复杂度本来看的就是近似值，多几个结点并不影响最终结果)

---

通过上面的计算，我们可以得出：向上调整建堆的时间复杂度为O(N)，向下调整算法时间复杂度为O(NlogN)。下面是N取不同值时两种复杂度大约要执行的次数

---

我们明显可以看出【向下调整建堆】优于【向上调整建堆】，具体表现在向下调整随着层数增加每个结点的调整次数会递减，而向上调整正好相反。层数越高需要调整的结点越多，因此总体来看向下调整建堆的总调整次数会更少。我们后面的建堆均会使用向下调整来建堆。

四. 堆的应用----蒜蓉叫花鸡

学了这么多堆的概念与操作，可能会有小伙伴们有疑问，我们如此费劲心思来创建的堆究竟有什么用呢？下面，我们就来介绍一下有关堆的两个应用：堆排序和TopK问题。

        4.1 堆排序

        所谓堆排序，就是利用大堆堆顶最大，小堆堆顶最小的思想来进行排序。假设有如下数组：

现要求我们使用堆排序对其进行升序排列，我们该怎么做呢？建大堆还是小堆呢？

int array[] = {27,15,19,18,28,34,14};

        由于是升序，我们首先想到的就是建小堆：

        建完小堆后我们就能将最小的数移动到数组前面，但当我们再想调整第二小的数时就碰到了一个问题：如果将数组剩余的元素看作堆，堆的关系就全乱了，我们需要重新建堆：

据此我们可以得出：如果我们采用升序建小堆的方法，每次选数都要重新建堆，而建堆的时间复杂度最快为，共有N个数，整体排序的时间复杂度就为。这效率肯定是不符合堆高端的身份的，不要急，我们再来看看升序建大堆的方法

        大堆的特点是堆顶元素最大，即我们建完大堆后最大的元素就到了我们数组的最前方：

         建完堆后我们要做什么呢？由于我们进行的是升序排列，所以我们先将堆顶的【34】和数组尾的【14】进行交换，然后进行下一次选数。这时除了根结点【14】之外，左右子树依然还是大堆，因此只需对堆顶元素【14】进行向下调整即可将剩余的数重新变为大堆。是不是很熟悉？没错，这里用到的思路和堆的删除是类似的

         对上面整个数组进行堆排序的具体过程和代码如下：

//堆排序，升序
void HeapSort(Hp* php)
{
	//先使用向下调整建大堆
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php, i, php->size);
	}

	for (int i = php->size - 1; i > 0; i--)
	{
		Swap(&php->a[i], &php->a[0]); //交换堆顶元素和堆尾元素
		AdjustDown(php, 0, i); //堆顶元素向下调整
	}
}

 那么，升序建大堆的时间复杂度是多少呢？

---

参照代码分析：首先向下调整建堆的时间复杂度为O(N)，然后每次交换后对堆顶元素进行向下调整的时间复杂度为O(logN)，共循环N-1次，因此整合后的时间复杂度为O(N+NlogN)。

由于N相对NlogN来说影响甚小，因此堆排序最终的时间复杂度为O(NlogN)

---

最后再来回到我们最初的问题：升序建大堆还是小堆？答案想必已经显而易见了，我们直接给出结论：

• 升序排列建大堆
• 降序排列建小堆 

        4.2 TopK算法

        介绍完堆排序后，我们再来看看另一个与堆息息相关的问题：TopK问题

        所谓TopK，即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
例如：统计专业前10名、世界500强、富豪榜、游戏战力排行榜中前100的活跃玩家等。

        对于此类问题，我们第一时间想到的可能就是进行排序了，将所有数据进行排序后取前K个就好了，这有什么难的？确实，如果数据量较小时可以这么做；但是，如果数据量非常大，排序的方法就不太可取了(毕竟数据可能都不能一下子全部加载到内存中，更别谈排序了)。

TopK问题的基本思路如下：

1、将数据集合前K个数据建堆

• 求最大K个-->建小堆
• 求最小K个-->建大堆

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

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

---

TopK问题的举例分析如下：

例如我们要求最大的K个数，则我们应该建小堆，小堆中的元素就是当前最大的K个数。由于小堆的堆顶最小，因此如果后面的数据大于堆顶元素，我们就需要将这个数据替换进堆，和谁替换呢？当然是和堆中最小的数据也就是堆顶数据替换，然后再向下调整为小堆即可。

---

TopK问题的 具体代码如下：

//用于交换数据
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整建小堆
void AdjustDown(int* a, int parent, int n)
{
	int child = 2 * parent + 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 = 2 * parent + 1;
		}
		else//满足小堆条件，直接返回
		{
			break;
		}
	}
}

//造大量数据，将数据存放到文件中
void CreateNDate()
{
	int n = 10000;
	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() % 1000000;
		fprintf(fin, "%d\n", x); //存入文件
	}

	fclose(fin);
	fin = NULL;
}

//打印前K个最大的数
void PrintTopK(int k)
{
	//1.申请大小为K的空间存放前K个元素
	int* kmin = (int*)malloc(sizeof(int) * k);
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL) //文件打开失败
	{
		perror("fopen error");
		return;
	}

    //2.将文件前K个数据读到数组中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout,"%d", &kmin[i]);
	}

	//3.前k个数向下调整建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kmin,i,k);
	}

    //4.读取文件剩余数据进行比较
	int data = 0;
	while (fscanf(fout, "%d", &data) == 1)
	{
		//比top-K小堆的堆顶大，替换
		if (data > kmin[0])
		{
			kmin[0] = data;
			//向下调整使其维持一个小堆
			AdjustDown(kmin, 0, k); //向上调整算法
		}
	}

	//5.打印top-K
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kmin[i]);
	}
	printf("\n");
	fclose(fout);
	fout = NULL;
}

int main()
{
	CreateNDate();
	PrintTopK(5); //打印前5个
}

---

TopK问题的复杂度分析如下：

首先，我们需要申请一个大小为K的空间来存放堆，空间复杂度为O(K)。其次忽略造数不谈，建堆的时间复杂度为O(K)，每次替换后向下调整的时间复杂度为O(logK)，最坏需要调整N-K次。因此忽略影响较小者后时间复杂度为O(NlogK)。

五. 堆的其余接口----酸梅汤

因为堆采用的是顺序存储方式，其余的接口如初始化、销毁、判空等操作都与顺序表相同。品尝了那么多大鱼大肉，总该解解腻。下面就不再过多赘述了，直接上代码

        5.1 堆的初始化

#define InitSize 4
void HeapInit(Hp* php)
{
	assert(php);
    //申请初始空间
	HeapDataType* tmp = (HeapDataType*)malloc(InitSize * sizeof(HeapDataType)); 
	if (tmp == NULL) //申请失败
	{
		perror("malloc fail\n");
		exit(-1);
	}
	else //申请成功
	{
		php->a = tmp;
		php->capacity = InitSize;
		php->size = 0;
	}	
}

        5.2 堆的销毁

void HeapDestroy(Hp* php)
{
	assert(php);
	free(php->a); //释放堆空间
	php->capacity = php->size = 0;//大小容量置0
}

        5.3 堆的扩容

static void CheckCapacity(Hp* php)
{
	assert(php);
	if (php->capacity == php->size) //堆满，进行扩容
	{
        //2倍扩容
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, php->capacity * 2 * sizeof(HeapDataType));
		if (tmp == NULL) //扩容失败
		{
			perror("realloc fail\n");
			exit(-1);
		}
		else //扩容失败
		{
			php->a = tmp;
			php->capacity *= 2;
		}
	}
}

        5.4 堆的判空

int HeapEmpty(Hp* php)
{
	assert(php);
	return php->size == 0; //等于0则为空，返回1;不等于0则不为空，返回0
}

        5.5 取堆顶元素

HeapDataType HeapTop(Hp* php)
{
	assert(php);
	assert(!HeapEmpty(php)); //确保堆不为空
	return php->a[0]; //堆顶元素就是数组中第一个元素
}

        5.6 堆的元素个数

int HeapSize(Hp* php)
{
	assert(php);
	return php->size;
}

以上，就是本期的全部内容啦🌸

制作不易，能否点个赞再走呢🙏