【数据结构】堆

堆是一种特殊的树，所以在了解堆之前，需要先学习树。

1、树的概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根节点没有前驱结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。

注意：树形结构中，子树之间是不能有交集的，否则就不是树形结构

1.2树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3树的结构定义

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

2、二叉树的概念及结构

2.1二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

2.3二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为n , 度为2的分支结点个数为m ,则有n=m+1.
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1).(ps：是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

        1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
        2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
        3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

6.在有n个结点的树中，一共有n-1条边，因为两两之间有一条边.

3、堆的概念及结构

3.1二叉树的存储方式

3.1.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

3.1.2链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，一般是二叉链，像红黑树等高阶数据结构会用到三叉链。

3.2堆的概念及结构

堆就是一颗完全二叉树，因为其结构的特殊性，存在数组中不会造成空间浪费，所以通常用数组来保存堆，堆分为小堆和大堆。

1、大堆：每个父亲都大于孩子，根(堆顶)的数据就是整棵树的最大值.

2、小堆：每个父亲都小于孩子，根(堆顶)的数据就是整棵树的最小值.

4、堆的代码实现

4.1堆的初始化(建堆)

由前面的讲解可知，我们会用数组来实现堆，所以堆可以定义为：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

建堆时，有向上调整法和向下调整法

以下讲解我们以建小堆为例.

4.1.1向上调整法

向上调整法即将除了根结点以外的所有结点，都与其到根之间的所有结点比较一下，如果这个结点小于父亲，就让其与父亲交换，然后再继续往上比较，直到该结点到根结点为止.

图中显示的即为向上调整法的调整顺序

当我们建堆时，通常会直接传过去一个数组，这样时间复杂度更低

void AdjustUp(HPDataType* a, int n, 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 HeapInit(Heap* php, HPDataType* a, int n)
{
	php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->_a == NULL)
	{
		printf("申请内存失败\n");
		exit(-1);
	}
	memcpy(php->_a, a, sizeof(HPDataType) * n);
	php->_size = n;
	php->_capacity = n;
	//现在是把所给的数组放进堆了，但是现在数组的顺序是任意的，所以还要进行排序
	//构建堆
	for(int i = 1;i < n;i++)
    {
        AdjustUp(php->_a , n , i);
    }
}

向上调整法建堆的时间复杂度是多少呢？

通常算时间复杂度时都是看最坏时间复杂度，所有我们直接用满二叉树来计算.

4.1.2向下调整法

与向上调整法类似，向下调整法就是从上面往下面比较.

注意：向下调整法的前提是左右子树都是小堆，所以这里的第一个调整对象是最后一个结点的父亲结点(也就是倒数第一个非叶子结点).

图中显示的即为向下调整法的调整顺序.

//前提：左右子树是小堆，因为现在实现的是小堆，如果实现的是大堆，那前提就是大堆
void AdjustDown(HPDataType* a, int n, int root)//向下调整算法的实现
{
	//找出左右孩子中小的哪一个
	int parent = root;
	int child = parent * 2 + 1;//直接默认左孩子小，然后再比较，这样子写会比直接定义一个LeftChild,一个RightChild更好
	while (child < n)//注意此时有一种极端情况可能会导致越界，即此时的结点有左孩子，但没有右孩子，所以第一个if还要加一个判断条件
	{
		//找出左右孩子中小的哪一个
		if (child + 1 < n && a[child + 1] < a[child])//此时若child+1>=n,也就是说这个结点只有左孩子，直接拿左孩子与父亲比较就可以了,若比较了child+1
			//则会造成数组越界
		{
			child++;
		}
		//如果孩子小于父亲就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;//这个时候的child是左孩子
		}
		else//如果孩子都大于父亲，那这个时候就是小堆，直接结束(此时是调到中间就结束了)
		{
			break;
		}
	}
}
void HeapInit(Heap* php, HPDataType* a, int n)
{
	php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->_a == NULL)
	{
		printf("申请内存失败\n");
		exit(-1);
	}
	memcpy(php->_a, a, sizeof(HPDataType) * n);
	php->_size = n;
	php->_capacity = n;
	//现在是把所给的数组放进堆了，但是现在数组的顺序是任意的，所以还要进行排序
	//构建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->_a, php->_size, i);
	}
}

向下调整法的时间复杂度是多少呢？

由上诉分析可知，向下调整法的时间复杂度更低，所以我们在实际应用中，建堆通常使用向下调整法.

4.2向堆中插入数据

向堆中插入数据时，物理上是在数组的末尾放入一个数据，但在逻辑上，是在二叉树的最后插入了一个结点，插入后这个二叉树不一定是堆，因为插入的数据会影响从这个位置，到根的路径上的所有结点，所有插入后，应该使用向上调整法，将这个结点到根上的所有结点比较一遍.

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	if (php->_size == php->_capacity)
	{
		php->_capacity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity);
		if (tmp == NULL)
		{
			printf("申请内存失败\n");
			exit(-1);
		}
		php->_a = tmp;
	}
	php->_a[php->_size++] = x;
	AdjustUp(php->_a, php->_size, php->_size - 1);
}

插入数据的时间复杂度是O(logN),因为就是进行了一次向上调整

4.3堆中删除数据(删除堆顶数据)

删除数据的思想很巧妙，是将堆顶的数据与最末尾的数据对换，然后将堆的大小减小1，然后来一次向下调整.

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);
	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;
	AdjustDown(php->_a, php->_size, 0);
}

删除数据的时间复杂度是O(logN),因为就是进行了一次向下调整.

4.4获取堆顶数据

HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);
	return php->_a[0];
}

4.5判断堆是否为空

bool HeapEmpty(Heap* php)
{
	return php->_size == 0 ? 1 : 0;
}

4.6堆的销毁

void HeapDestory(Heap* php)
{
	assert(php);
	free(php->_a);//注意这里只需要free这个php里面的_a即可，因为_a是malloc出来的，不能free(php),因为php是外面局部变量的地址，出了程序自然没了
	php->_a = NULL;
	php->_size = php->_capacity = 0;
}

5、堆的应用

5.1、堆排序

利用大堆的堆顶元素是整棵树最大的，小堆的堆顶元素是整棵树最小的，可以用堆来进行排序.

以建小堆为例，只需要每次都进行建堆，得到堆顶元素，然后将堆顶元素与堆的最末尾的元素进行交换，然后将堆的大小减小1，这样子堆中最小的元素就到了数组的最后面，因为此时堆的大小减小了1，所以最小的元素不会再被挪动，已经到了正确的位置，然后再依次选次小的，直到堆只剩下一个元素。

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

void HeapSort(HPDataType* a, int n)
{
	//1、建堆
	//for(int i = n-1;i>=0;i--);这个是把堆中每个数都用一次向下调整算法，但注意，这个的时间复杂度不是n*logn，而是O(n)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
    //2、将第一个数据与最后面的数据交换
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		//继续向下选次小的
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序的时间复杂度

建堆的时间复杂度是O(N)，

一共有N-1次交换，每次交换会从堆顶开始一次向下调整，所以时间复杂度是O(N*logN)

所以堆排序的时间复杂度是O(N*logN)

5.2 TOK问题

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。

void PrintTopK(Heap* php,HPDataType* a, int n, int k)
{
	assert(php);
	assert(a);
	// 1. 建堆--用a中前k个元素建堆
	php->_a = (HPDataType*)malloc(sizeof(HPDataType*) * k);
	for (int i = 0; i < k; i++)
	{
		php->_a[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->_a, k, i);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > php->_a[0])
		{
			php->_a[0] = a[i];
			AdjustDown(php->_a, k, 0);
		}
	}
}
void TestTopk(Heap* php)
{
	int n = 10000;
	HPDataType* a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	//srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(php,a, n, 10);
}
int main()
{
	Heap hp;
	TestTopk(&hp);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", hp._a[i]);
	}
	return 0;
}

这里要注意一个问题，如何判断选出的k个数就是最大或最小的k个数呢？

在代码中，我们可以将产生的随机数与1000000取模，这样子数组中的数据就都小于1000000了，然后再随机的在数组中找10个数，将其赋值成比1000000还要大的数，运行代码，看能不能找出被随机赋值的这10个数，如果找出来了，那么证明代码没有问题。

原文链接：https://blog.csdn.net/2301_80277275/article/details/136632438