数据结构——堆

目录

一、堆的定义

二、堆的存储结构

三、堆的实现

1、堆的存储

2、堆的初始化

3、堆的插入

向上调整

4、堆的删除

向下调整

5、取堆顶元素

6、判断堆是否为空

7、当前数据个数

8、释放

四、堆排序

1、向上调整建堆排序

2、向下调整建堆排序

3、建堆时间复杂度分析

五、topK问题

---

一、堆的定义

堆的本质是一个二叉树。与二叉树的区别在于：对于这颗二叉树而言，任何一个子树根节点上的数据和孩子节点上的数据之间是存在一种关系的。根据这种关系堆又可以分为大根堆和小根堆。

1、大根堆

大根堆根节点上的数据大于或者等于左右两个孩子大的。看下面的图就很容易明白了。

2、小根堆

明白了大根堆后，小根堆大家一想便知道了吧，根节点上的数据小于或者等于左右两个孩子小的。?

这个时候肯定就要有人问了，如果这颗树的所有数据都一样呢？叫大根堆还是小根堆呢？? 理论上来说可以叫大根堆也可以叫等根堆。

二、堆的存储结构

这里我就直接介绍一种最方便的存储结构，就是直接用数组来存储。

我相信大家看到这里肯定会有一种疑惑，这是一个二叉树啊？能用数组表示吗？这就好像有点天马行空的感觉，但其实如果我们细细分析其实还真的可以。我们就用下面这个大根堆为例。

当我们把它的每一层都放到数组里面，如果我们仔细观察这个数组就可以发现是有规则的。规则就是如果我们知道父亲的下标，就可以计算出它的左孩子和右孩子的下标。如果我们知道左孩子或者右孩子的下标，我们也可以计算出父亲节点的下标。

1、知道孩子的下标，如果知道父亲的下标呢？ parent = (child - 1 ) / 2;?

这里的child可以是左孩子的下标也可以是右孩子的下标。举个例子大家就明白了。比如说79的下标是5,（5 - 1）/ 2 的结果是2，它的父节点的下标就是2。如果是它的右孩子呢？(6 - 1) / 2的结果还是2，注意这里不是数学计算，而是C语言的结算结果。

2、知道父亲的下标，如果知道左孩子下标呢？ leftchild = parent * 2 + 1;

3、知道父亲的下标，如果知道右孩子下标呢？rightchild = parent * 2 + 2;

在写代码实现堆的时候会用到上面这几点的。

tips: 1、并不是所有的语言都可以用数组存储二叉树，如果一门语言它的计算规则是向上取整就不可以用数组来存储。换言之，C语言可以是因为它是向下取整的。

? ? ? ? 2、并不是所有的二叉树都是适合用数组来存储的，如果一颗二叉树存在空节点，就很容易造成空间浪费的问题。也就是说只有完全二叉树适合用数组存储。

三、堆的实现

这个地方先说一下，下面堆的插入删除什么的都是默认以大根堆的形式实现的。

1、堆的存储

我们要实现堆第一个问题就是，它的底层结构是什么？当然是数组，刚刚我们已经提到过了。那么还需要什么呢？当然是capacity(容量)和size(当前数据个数)。

typedef int DataType;
typedef struct Heap
{
	DataType* a;
	DataType size;
	DataType capacity;
}heap;

这里地方可能会有些疑问，就是为什么要把int重命名一下呢？直接用不就好了吗？如果我们直接用就会发生什么问题呢？问题就是这个堆不一定就是存储整形的，我们也可以用来存储浮点数，甚至一个结构体，此时如果要改代码的话许多地方都需要改。会很麻烦，如果我们重命名一下我们要改动只需要改动一个地方就可以。C++或者其它一些语言会有更好的解决方法。这里我们这样处理会比较ok一点。

2、堆的初始化

初始化很简单，给数组开点空间然后修改capacity和size即可。

void HeapInit(heap* php)
{
	assert(php);
	php->a = (DataType*)malloc(sizeof(DataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}

3、堆的插入

这里的第一个问题就是容量的问题。有可能我插入一个数据的时候容量不够，如果容量不够就需要干嘛，就需要扩容。如果容量是够的，我们直接插入数据然后更新size是不是就可以呢？大家思考一下是不是就可以呢？其实是不可以的，因为你要保证这颗树满足大根堆或者小根堆的性质呀，因此当我们插入数据之后我们是需要调整一下的，那么如何调整呢？

向上调整

假设我们要建的是一个大根堆，现在这个堆是39、15、24、7。现在新插入了一个数46。那么我们首先要找到46的父亲，然后看看46是否比它的父亲大，如果46大于它的父亲，就把它们两个交换，然后在继续迭代往上判断。如果不大于说明它就是一个大根堆。如果是一个大根堆，直接结束。看下面的图就很容易理解了。

看懂了之后就来实现一下向上调整吧。?

我们先来想一下这个函数应该如何设计。需不需要返回值呢？不需要返回值。因此返回值直接void，函数参数呢？你肯定要把数组给我吧？然后呢，你还要给我孩子的下标吧？不然我咋算出父亲下标呢。有这两个就Ok了。函数名就AdujustUp吧。这里的代码大家可以自己尝试实现一下，写出来在和我写的代码对比一下。这里写代码大家可以对照着上面的写，很容易就写出来了。这里交换的函数我就不写出来了，应该都会写吧。

向上调整代码：

//左右子树必须是大堆或者小堆。
void AdujustUp(DataType* 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;
		}
		
	}
}

下面是堆插入的代码:

void HeapPush(heap* php, DataType x)
{
    assert(php);
	if (php->size == php->capacity)
	{
		DataType* tmp = (DataType*)realloc(php->a, sizeof(DataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

	AdujustUp(php->a, php->size - 1);

}

4、堆的删除

这里就有一个问题了，删谁？大家想一想堆要删除删除谁呢？是删除最后一个元素吗？可以，但是删除最后一个元素有没有意义？没有任何意义，一个大根堆，你把堆尾最后一个元素删了老大还是那个老大。但是如果你把老大干掉了老二是不是就能登场了？因此我们要删就把老大删了。那么如何删呢？挪动数据吗？挪动数据肯定是不行的，挪动数据的话那堆就乱完了，父亲不是父亲儿子不是儿子了，而且效率还贼低。所以我们要采取另一种方法，就是直接把老大(堆顶元素)和老末(堆底的最后一个元素)换了。请看下图

交换完成之后，就完了吗？当然不，我们要确保这是一个大根堆，因此我们需要调整，这个调整专业叫法叫做向下调整。?

向下调整

我们怎么调整呢，肯定是从根开始往下调，我们就以上面的8，25,21,25,16为例，这里4相当于已经被删除了，因此不将它看成堆的一部分。那么我们从8这个位置开始调整，8肯定是要和它的孩子比较的，那么和谁比较，一定是要和两个孩子大的那一个比较，至于为什么大家可以思考一下就可以得出答案。如果是比大的那个孩子小的话，就交换，交换之后，继续向下调整。如果比大的那个孩子大，就停止调整。

同样的，思考一下如何写代码，首先需不需要返回值，不需要。其次，要传什么参数，你肯定要给我一个数组，然后，还要有堆的数据个数，数据个数用来作为循环的结束条件。还要给我父亲的下标。这里要注意的是要父亲要和左右孩子大的那个进行比较，这里可以假设一下，具体可以看我下面的代码。?

?向下调整代码：

//左右子树必须是大堆或者小堆。
void AdujustDown(DataType* 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[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

对照着上面的图看代码就非常清晰了。

下面是删除的代码:

void HeapPop(heap* php)
{
    assert(php);
    assert(!empty(php));
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdujustDown(php->a, php->size, 0);

}

5、取堆顶元素

DataType top(heap* php)
{
    assert(php);
	return php->a[0];
}

6、判断堆是否为空

bool empty(heap* php)
{
    assert(php);
	return php->size == 0;
}

7、当前数据个数

size_t Size(heap* php)
{
    assert(php);
	return php->size;
}

8、释放

void destroy(heap* php)
{
	free(php->a);
	php->capacity = php->size = 0;
}

四、堆排序

我相信大家在刚刚学习堆的过程中，一定会发现堆是非常适合用来排序的。因为可以很快选出最大的或者最小的。那么堆如何用来排序呢？我们要利用堆的删除思想进行排序。

1、向上调整建堆排序

比如说现在给了你一组数：9,5,1,4,2,7,6,8,10,3。要把它排成升序的，这里有同学可能会说我建一个小堆，然后让这些数据进堆，然后依次top，取出最小的，放到这个数组里。可以是可以，但是难道你每次排序前都有一个堆吗？如果没有堆你还要手搓一个堆？是很麻烦的。可不可以直接就用这组数建堆，就是说，我把每一个数依次看成是插入的元素，就是说我把5、1、4、2、7、6、8、10、3看成插入的数，向上调整，就可以完成建堆的操作。

好，现在第一个问题来了，我要排成升序的，我建大堆还是小堆，大家可以思考一下。有同学可能会觉得建个小堆，直接就能取到最小的那个，没错，你取到最小的那个是方便了，但是你如何取到第二小的呢？当取到最小的那个的时候，我们就要把它不看做堆里的元素，注意，这里我们是在这个数组进行建堆的，是没有堆这个数据结构的，只有向下调整和向上调整。那么我们只能把剩下的数据进行建堆，然后依次进行。那这样还不如我在数组里依次比较呢。因此我们排升序要建大堆。然后将数组的第一个元素和最后一个元素交换。交换完成之后，把最后一个元素不看做堆里的元素，然后进行向上调整。

代码：

void HeapSort(int* a, int n)
{
	//向上调整建堆
	for (int i = 1; i < n; i++)
	{
		AdujustUp(a, i);
	}


	int end = n - 1;
	while (end > 0)
	{
		swap(&a[end], &a[0]);
		AdujustDown(a, end ,0);
		--end;
	}
}

其实是非常简单的，比冒泡排序复杂不了多少。 大家可以对照着下面这张图来看。

2、向下调整建堆排序

刚刚我们其实是模拟插入的过程建的堆，那还有没有其它建堆的方式呢？现在随便给了一组数70,65,100,35,50,600，怎么建堆呢，还可以向下调整建堆。但是我们能从根开始直接向下调整吗？是不可以的。因为这是随便给你的一组数，你不能保证你的左孩子或者右孩子就是最大的那个，向上调整和向下调整是有条件的，左右子树必须是大堆或者小堆才可以。接下来就以这组数为例:9,5,1,4,2,7,6,8,10,3 。

我们不能从根开始调，那从哪里开始调呢，难道从叶子结点开始吗？可以，因为叶子可以看成一个大堆也可以看成一个小堆，但是从叶子调没必要。那倒着调从哪个位置调整呢？从最后一个叶子的父亲开始调就可以。调整的顺序是2,、4、1、5、9.

代码：

void HeapSort(int* a, int n)
{

	//向下调整建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdujustDown(a, n, i);
	}


	int end = n - 1;
	while (end > 0)
	{
		swap(&a[end], &a[0]);
		AdujustDown(a, end ,0);
		--end;
	}
}

3、建堆时间复杂度分析

既然有两种建堆方式，那我们是用向上调整建堆还是向下调整建堆呢？结论是用向下调整建堆，因为向下调整建堆的时间复杂度是O(N),向上调整的时间复杂度是N*log(N)。感兴趣的同学可以看一下下面的证明。

向下调整时间复杂度证明：

以最坏的情况满二叉树为例。我们知道向下调整建堆是从倒数第二个层开始调整的。倒数第二层的节点个数是2^(h-2)，这个相信大家都没问题吧，在倒数第二层的时候你最多向下移动几次呢？是不是就是一次呀，你最下面就只有一层，因此只可能向下移动一次，倒数第三层的时候是2^(h-3),此时最多向下移动3次，因此，我们假设建堆的总次数是T(N)，那么，就可以得出下列的公式，然后用错位相减法，用2T(N)-T(N)，可以发现相减之后是一个等比数列，因此就可以得到一个结果就是T(N) = 2^h - 1 - h,前面2 ^ h - 1是二叉树的节点总个数，因此时间复杂度就是O(N)的。

向上调整时间复杂度证明：?

向上调整的时候是从第二层开始，因此第二层最多向上移一层，第三层最多向上移动二层，以此类推，因此假设T(N)为总建堆次数，然后将这些相加，之后用错位相减法。

其实这里你一看就知道向上调整时间复杂度要高。因为它是一个双多的情况，你节点少的时候层数少，因此你越往下层数越高，节点个数越多。最后一层的节点个数就占了整个节点数的一半，高度还特别高。而向下调整不一样，最后一层它只需要调整一次，越往上节点越少，调的次数多一点也没啥关系。?

五、topK问题

比如说现在有10亿个数据，要你选出其中最大的50个数，应该怎么选？这里我就直接说结论了，就是我们可以建一个容量50的小根堆，然后先把前50个数据丢到堆里，之后依次遍历剩余的数据，将比堆顶大的数据代替堆顶进堆。大家思考一下这里为什么要建小堆。其实很简单，小堆堆顶的元素一定是最小的，因此比堆顶大的元素就会沉在最下面。如果是大堆，如果刚开一就来了最大的，那其它元素就被卡死了进不去了。

接下来我们直接用代码实现一下，我们实现的简单一点，就建一个文件，然后文件里搞10000个数据，找出前10大的数。

#include <time.h>
#include <stdio.h>

void PrintTopk(const char* file, int k)
{
	//1、建堆
	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);

	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//读出前k个数据建小堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &topk[i]);
	}

	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdujustDown(topk, k, i);
	}

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

	for (int i = 0; i < k; i++)
	{
		printf("%d ", topk[i]);
	}
	printf("\n");
	free(topk);
	fclose(fout);
}

//造数据
void CreatData()
{
	srand((unsigned)time(NULL));
	const char* file = "num.txt";
	FILE* fp = fopen(file, "w");
	if (fp == NULL)
	{
		perror("fopen fail");
		return;
	}

	for (int i = 0; i < 10000; i++)
	{
		int x = rand() % 10000;
		fprintf(fp, "%d\n", x);
	}

	fclose(fp);
}


int main()
{

	//CreatData();
	PrintTopk("num.txt", 10);

	return 0;
}

这里每一次你执行程序都会产生不同的文件内容，因此可以造完数据之后就将它屏蔽掉，之后你如何知道这10个数就是最大的呢？有一种很6的做法就是，你直接去把文件里面的数据修改一下，自己修改10个最大的。如果执行的结果是这10个数，就说明代码没有问题。

欧克欧克，希望堆大家有所帮助。byby