堆

定义：什么是堆？

从堆的定义上我们可以看出，堆在物理结构上是一维数组，逻辑结构上，可以把堆理解为一棵完全二叉树，因为堆满足ki<=k2i+1，ki<=k2i+2(ki>=k2i+1，ki>=k2i+2)，而我们了解对于完全二叉树，父结点和孩子结点存储在一维数组中有如下的下标关系：

• leftchild=parent*2+1
• rightchild=parent*2+2=leftchild+1

与堆的下标关系是完全吻合的，所以在逻辑上我们可以把堆理解为一颗完全二叉树。

给定一个任意的一维数组，在逻辑上，我们可以将其理解为一颗完全二叉树。

此时一维数组只是一颗完全二叉树，还并不是堆，堆还需要满足：对一维数组中任意一个ki，有：

体现在逻辑结构上：该棵完全二叉树及其任意一棵子树均满足父结点小于等于左右孩子结点的值或者是父结点大于等于左右孩子结点的值。

堆的分类：

根据父结点与左右孩子结点值的关系，可以将堆分为两类：

大根堆：

父结点大于等于左右孩子结点的值，每一棵子树都满足这个条件，则整棵树的根节点是这棵树上值最大的结点。故称为大根堆。

小根堆：

父结点小于等于左右孩子结点的值，每一棵子树都满足这个条件，则整棵树的根节点是这棵树上值最小的结点。故称为小根堆。

所以我们需要对上述的还不是堆的完全二叉树做出调整，使之成为堆，接下来向大家介绍调整一维数组建立堆的过程。

建堆方法：

建堆有两种方法：

分别是向上调整建堆和向下调整建堆：

向上调整建堆：（以建立小根堆为例）

如果堆中只有一个元素，即对应的完全二叉树只有一个根结点，我们认为他已经是堆了。红色圈的元素表示已经建立并维持堆。

接下来我们插入第二个元素4，判断其与其父节点是否满足父节点的值小于等于孩子结点的值，满足所以无需调整，仍维持堆。继续向堆中加入下一个元素3。

判断其与其父节点是否满足父节点的值小于等于孩子结点的值，满足所以无需调整，仍维持堆。继续向堆中加入下一个元素1。

判断1与其父节点是否满足父节点的值小于等于孩子结点的值，不满足，则交换父节点与子节点的值，以维持小根堆。

调整后发现1作为左孩子所在的子树不满足堆的结构了，需做出调整，此时应从左右孩子（1，3）中选出较小的那个与父节点（2）交换，以维持小根堆。

1作为较小的孩子与父节点2交换，以维持小根堆结构。交换后，满足小根堆的条件，继续向堆中插入元素8并调整维持小根堆。

元素8插入小根堆后，满足小根堆，无需做出调整，继续向小根堆插入元素6。

元素6插入小根堆后，满足小根堆，无需做出调整，继续向小根堆插入元素7。

...继续按上述步骤，直到全部元素进入小根堆并且通过向上调整维持小根堆。

至此，通过向上调整的方法成功建立了小根堆。

核心代码：

void AdjustUp(int* a, int child, int sz)//向上调整建堆--以小根堆为例
{
	int parent = (child - 1) / 2;
	while (parent >= 0)
	{
		if (a[parent] > a[child])
		{
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			child = parent;
      parent= (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整建堆：（以建立小根堆为例）

前面已经提到，如果完全二叉树中只有一个结点，则我们认为他是堆，那么对于已有的一棵完全二叉树，可认为其所有的叶子结点已将全部是堆。

那么对于本例中的完全二叉树的叶子节点，可以认为他们已经是堆了。我们需要从最后一个非叶子结点开始调整建堆，插入建堆，也就是结点1，开始向下调整。

而最后一个非叶子结点的坐标与最后一个叶子结点坐标有关，最后一个非叶子结点是最后一个叶子节点的父节点，利用parent=(child-1)/2可以求出最后一个非叶子节点的坐标。

先选取最后一个非叶子结点1，判断其与其孩子节点是否满足小根堆的条件，即根结点的大小小于等于左右孩子结点的大小。满足，则无需调整，1插入堆中。

选取下一个非叶子结点3，判断其与其孩子节点是否满足小根堆的条件，满足，则无需调整，3插入堆中。

选取下一个非叶子结点4，判断其值与其孩子节点值是否满足小根堆的条件，不满足小根堆，选择左右孩子中较小值结点与父节点4交换。

交换后，以4为父节点的子树要继续判断是否满足小根堆条件，如果不满足仍要选择较小的孩子结点继续交换以维持小根堆的结构。本例中满足小根堆，所以无需交换，1插入到堆中，并维持小根堆。继续插入下一个非叶子结点。

选取下一个非叶子结点2，判断其值与其孩子节点值是否满足小根堆的条件，不满足小根堆，选择左右孩子中较小值结点与父节点2交换。

2作为换下来的结点，继续判断以2作为父节点的子树是否维护小根堆，如果不满足，则继续向下调整，选取左右孩子中较小的与父节点交换，一直到满足小根堆或者是调整到叶子结点。本例中以2作为父节点的子树满足小根堆，所以无需调整，1插入小根堆中，所有非叶子节点已经调整完毕，则小根堆的向下调整建立已经建好。

至此，通过向下调整的方法成功建立了小根堆。

核心代码：

void AdjustDown(int* a, int parent, int sz)//向下调整建立小根堆，parent是父节点下标，sz是数组元素个数 int*a等价于int a[]
{
	int minchild = 0;
	while (parent < sz)
	{
		int leftchild = parent * 2 + 1;//根据父节点下标求解左右孩子结点坐标
		int rightchild = leftchild + 1;
		if (leftchild < sz)
		{
			if (rightchild<sz)//找出两个孩子结点中值较小的结点
			{
				minchild = a[leftchild ]< a[rightchild] ? leftchild : rightchild;
			}
			else
			{
				minchild =leftchild;
			}
			if (a[parent] > a[minchild])//不满足小根堆条件，需要交换子节点和父节点的值
			{
				int tmp = a[minchild];
				a[minchild] = a[parent];
				a[parent] = tmp;
				parent = minchild;
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
}

void TestHeap()
{
	int a[] = { 9,0,1,5,3,7,2,8,6,9 };
	int sz = sizeof(a) / sizeof(int);

	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, sz);//向下调整建堆，从最后一个非叶子结点开始调整，一直到下标为0的非叶子节点。
	}

}

通过以上两种方法可以实现堆的建立。本例以小根堆的建立为例，大根堆的建立同理，大根堆要满足二叉树中任意一棵子树的父节点的值要大于等于左右孩子结点的值。不满足时需要一直向下/向上调整，直到满足大根堆的条件停止。

堆的应用：

应用1：堆排序

通过以上建堆的过程分析，我们可以看到，建立堆后，如果建立的是大根堆，那么数组首个元素，也就是堆顶，对应二叉树的根节点，是整个数组中的最大值，如果建立的是小根堆，则其数组的首个元素则是整个数组中的最小值。

那么我们可以想到，建立堆的过程可以帮助我们找到一组数值中的最大/小值，那么如果有n个无序数字，我们可以通过多次建堆来找到最大/小值，次大/小值，第三大/小的值...第n大/小的值，这其实也是堆排序的思想。

那么堆排序是如何实现的呢？（以n个无序整数数组a排序，建堆时建立小根堆为例）

1）首先利用向上调整/向下调整的方法建堆，假设我们建立的是小根堆。

2）建立小根堆以后，堆顶元素是整个序列中的最小值，交换堆顶元素与堆的最后一个元素，则序列中最小的元素就到了a[n-1]，原来的最后一个元素到a[0]位置，（可以先让大家了解其实建立小根堆可以实现降序排序）此时除了a[0]和a[n-1]以外，数组中别的元素仍满足小根堆的结构。

3）如果a[0]不满足小根堆，则对其进行向下调整，使之满足小根堆的结构，但是在调整过程中，原来被交换下去的堆顶元素a[n-1]不可以参与调整，原因是建立小根堆实现的是降序排序（具体原因在后面讲），那么最小值到a[n-1]则认为这个数已经在排序结束后的正确的位置上了，所以a[n-1]元素不再参与堆的调整了。

4）则最后一个数不参与调整，则调整范围就变为了[0,n-2]，a[0]向下调整结束后，[0,n-2]范围内的最小值就位于堆顶a[0]了，交换a[0]与a[n-2]，则整个待排数组中次小的数到达a[n-2]的位置，继续对堆顶交换上去的元素进行向下调整（如果不满足小根堆的情况下），再交换a[0]与a[n-3]，继续调整，交换，调整.....直至交换了a[0]与a[1]，则认为[1,n-1]都已有序，则a[0]自动有序。

5）此时建立小根堆的堆排序完成。

通过以上分析，我们还能得出两个结论：

建立小根堆，交换调整，最终可以实现降序排序。

建立大根堆，交换调整，最终可以实现升序排序。

代码：（以小根堆为例，则实现的是降序排序）

void AdjustDown(int* a, int parent, int sz)
{
	int minchild = 0;
	while (parent < sz)
	{
		int leftchild = parent * 2 + 1;
		int rightchild = leftchild + 1;
		if (leftchild < sz)
		{
			if (rightchild<sz)
			{
				minchild = a[leftchild ]< a[rightchild] ? leftchild : rightchild;
			}
			else
			{
				minchild =leftchild;
			}

			if (a[parent] > a[minchild])
			{
				int tmp = a[minchild];
				a[minchild] = a[parent];
				a[parent] = tmp;
				parent = minchild;
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void HeapSort(int* a, int sz)//堆排序-有sz个元素的整型数组a
{
	//1.建堆
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)//从最后一个非叶子结点开始向下调整
	{
		AdjustDown(a, i, sz);
	}
	//建好堆，此时a[0]处是数组中的最小值，交换，继续调整
	swap(&a[0], &a[sz - 1]);
	for (int i = 0; i < sz - 1; i++)//重复sz-1次交换调整
	{
		AdjustDown(a, 0, sz - 1 - i);
		swap(&a[0], &a[sz - 1 - 1 - i]);
	}
}

测试结果展示：

应用2：TopK问题

应用场景以及问题描述:

如果给定的数据海量，我们想要获取最大/最小的前k个数，比如说世界500强等，我们当然可以通过对所有数据排序解决，但是数据的数量很多时，时间开销就会大大增加。且内存中可能存储不下过多的数据。

最好的方法就是利用堆来实现。

解决思路：

1）用数据集前k个元素建堆

求前k小个元素建大根堆。

求前k大个元素建小根堆。

2）用剩余的n-k个元素分别与堆顶元素值比较，不满足堆就替换堆顶并调整。

以求前k个最大的数为例。

例如：求前k大的数据，则先用前k个元素建立小根堆，则处于堆顶的元素就是这k个数中最小的数，用剩余的n-k个数与堆顶比较，如果有数比堆顶还大，则用这个数替换堆顶并调整，保持使这k个数中最小的数始终位于堆顶，则全部把剩余的n-k个数遍历完成后，最大的k个数就在堆中了。

即：每次能换进来的是比堆顶大的数，而换出去的是k个数中最小的。（堆顶始终是k个数中最小的数）

我们通过程序验证一下：

void testTopK()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % 100000;//生成小于100000的n个随机数
	}
	a[4] = a[4] + 100000;//手动设置k个最大值
	printf("%d ", a[4]);
	a[136] = a[136] + 100000;
	printf("%d ", a[136]);
	a[999] = a[999] + 100000;
	printf("%d ", a[999]);
	a[6851] = a[6851] + 100000;
	printf("%d ", a[6851]);
	a[10004] = a[10004] + 100000;
	printf("%d ", a[10004]);
	a[1208] = a[1208] + 100000;
	printf("%d ", a[1208]);
	a[47] = a[47] + 100000;
	printf("%d ", a[47]);
	a[5431] = a[5431] + 100000;
	printf("%d ", a[5431]);
	printf("\n");
	//求前8个大的数以及下标
	int pos[9] = { 0 };
	int cnt = 0;
	for (int i = (8 - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, 8);//前k个数向下调整建堆
	}
	for (int i = 8; i < n; i++)//遍历剩余的n-k个数，比堆顶大则交换进入，并向下调整维持堆
	{
		if (a[i] > a[0])
		{
			swap(&a[i], &a[0]);
			AdjustDown(a, 0, 8);
		}
	}
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	free(a);
	a = NULL;
}

测试数据：

可以看到控制台打印了我们设置的前k个最大值。

以上就是今天的全部内容啦！今天和大家分享了堆以及堆的应用，希望以上内容能帮你更好的理解堆以及堆排序，如果在文章中发现错误，欢迎在评论区留言或者是私信小Q，如果觉得文章不错希望给个一键三连，我们下一篇博客见！