数据结构——二叉树-堆(堆的实现，堆排序，TopK问题)

前言

1.树的概念及结构

1.1 树的概念

1.2 树的相关概念

1.3 树的表示

2. 二叉树的概念及结构

2.1概念

2.2 特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储结构

3. 堆

3.1 堆的概念及结构

3.2 堆的实现

3.1.2 数据结构的设计和文件准备

3.1.2堆的初始化和销毁

3.1.3 向下调整算法与向上调整算法

3.1.4 堆的插入和堆的删除

3.1.5 获取堆顶元素和堆的数据个数，堆的判空

3.3 建堆

4. 堆的应用

4.1 堆排序

4.1.2 思路

4.2.2 代码

4.1.3 时间复杂度的分析

4.2 TopK问题

4.2.1思路

4.2.2 代码实现

总结

前言

这篇文章介绍二叉树中的特殊的数据结构堆，堆的应用有堆排序和TopK问题。有详细的图文讲解，可以边看边敲，一起学起来吧！

1.树的概念及结构

1.1 树的概念

树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特定的节点被称为根节点或树根（root）。
除根节点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树（subtree）。
树是递归定义的。

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概念

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

从上图可以看出：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

且对于任意的二叉树都是有下面的几种情况合成的：

2.2 特殊的二叉树

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

2.3 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。
对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1。
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)。 (ps：是log以2为底，n+1为对数)。
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

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

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1.顺序存储

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

下图中，完全二叉树的春旭存储没有浪费数组空间，而非完全二叉树的存储，需要补齐一些树的空间，体现在数组中就是不存储有效值。没有填写有效值，会被系统赋值为随机值，浪费空间极大。

2.链式存储

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

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft;  // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data;            // 当前节点值域
}

我们下一个章节会讲解二叉链实现。

3. 堆

3.1 堆的概念及结构

堆通常是一个可以被看做一棵树的数组对象。堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。

堆总是满足下列性质：

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

3.2 堆的实现

在实现堆之前，需要准备三个文件，分别是Heap.h，Heap.c和test.c。

Heap.h文件用来存放堆的数据结构的设计和各种接口函数的声明。
Heap.c文件里面存放各种接口函数的实现。
test.c文件是用来写测试函数，检验接口函数的功能。

3.1.2 数据结构的设计和文件准备

堆的存储结构本质是数组，所以数据结构的设计跟顺序表相同，有一个数组，一个存储数据个数的值，另外一个存储数据容量大小。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php); 
//堆的插入
void HPPush(HP* php, HPDataType x);
//删除堆顶的数据
void HPPop(HP* php);
//获取堆顶数据
HPDataType HPTop(HP* php);
//堆的数据个数
int HeapSize(HP* hp);
//堆的判空
bool HPEmpty(HP* php);
//交换数据
void Swap(HPDataType* px, HPDataType* py);

3.1.2堆的初始化和销毁

堆的存储结构本质上是数组，所以初始化操作只需要把数组置空，数据个数和容量赋值为零即可。而堆的销毁只需要释放动态开辟的空间。

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

3.1.3 向下调整算法与向上调整算法

现在有一个数组，逻辑上看成一个完全二叉树。观察下图，根节点的左右子树都是小堆，但是根节点不满足堆的性质，不是最小的数。这个时候就可以使用向下调整算法使其变成一个小堆。

注意：只有左右子树都是小堆才能进行向下调整算法。（如果要调整大堆，左右子树就必须是大堆，如无特别声明，都是以小堆为主）

int arr[] = {27,15,19,18,28,34,65,49,25,37};

如下面所示，我们利用父亲结点和孩子结点的式子关系，让根节点和孩子节点比较，如果比孩子结点小，就交换。

leftchild = parent * 2 + 1
rightchild = parent * 2 + 2
parent = chlid - 1

代码如下，先写一个交换函数，因为后面的接口函数也会复用。

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
        //假设法，选出小的那个孩子
		if (child+ 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

与向下调整算法类似，向上调整算法需要保证这个完全二叉树满足堆的性质，在尾部插入一个数据，然后向上跟父亲结点比较大小，进行交换。

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)//parent > 0不行
	{
		if (a[child] < a[parent])//小堆
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3.1.4 堆的插入和堆的删除

堆的插入是在存储结构数组最后面插入一个数据，然后再使用向上调整算法，使其符合堆的性质。首先检查数据容量大小是否足够，不够就扩容。然后将x值插入到数组后面。

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

堆的删除一般指的是删除堆顶元素。将堆顶元素删除后，如果直接将孩子结点元素向上移动会破坏堆的结构。所以，合适的操作是先将堆顶元素与最后一个结点元素交换，再删除最后一个节点元素。对根节点进行向下调整算法，使其成为一个堆。

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

3.1.5 获取堆顶元素和堆的数据个数，堆的判空

获取堆顶元素和获取堆的数据个数比较简单。堆的判空直接返回数据个数是否为零的判断。

HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}

int HeapSize(HP* hp)
{
	return hp->size;
}

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

3.3 建堆

建堆就是通过使用堆的插入这个函数，将一个数组的逻辑结构转变成堆，然后我们使用while循环进行堆删除的操作，对删除是删除对顶的元素。

int main2()
{
	int a[] = { 50,100,70,65,60,32 };

	HP hp;
	HPInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}

	HPDestroy(&hp);
	return 0;
}

运行结果如下，我们会发现从小到大打印在控制台上，因为每次取堆顶元素，然后再进行堆的删除，堆顶元素是最小的元素，所以是升序打印。

4. 堆的应用

4.1 堆排序

4.1.2 思路

堆排序就是利用堆的性质进行排序。堆排序分为两个步骤：

1.建堆：

升序：建大堆
降序：建小堆

2.利用堆删除的思想来排序。

堆的性质是不管那个结点的值都不小于或者不大于父亲结点的值。假设我们要排升序，需要建一个大堆，那么根结点的值是最大。但要注意的是，使用向下调整算法建大堆，最后一层不用调整，要从最后一个叶子结点的父亲结点开始使用向下调整算法，一直到根结点。
接着跟堆的删除操作一样先将根节点的值和尾结点的值进行交换，此时尾结点就是最大的值。然后对此时的根节点使用向下调整算法，那么根节点的值是除了开始调整到尾结点的值中的最大值。
现在下面有一组数据，我们使用堆排序算法来排升序

int arr[] = { 11,8,3,5,21,15 }

4.2.2 代码

代码如下：

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
        //假设法，选出小的那个孩子
		if (child+ 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//a数组向下调整算法建堆
	for (int i = (n-1-1)/2;i>=0; i--)
	{
		AdjustDown(a, n, i);
	}

	//利用堆的删除的思想，只需要交换n-1次
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

int main()
{
	int a[] = { 50,100,70,65,60,32,26,43,82,54 };
	int size = sizeof(a) / sizeof(int);

	HeapSort(a, size);

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

	return 0;
}

结果如下：

4.1.3 时间复杂度的分析

堆排序主要分为两个部分一个是建堆，然后进行交换元素进行向下调整。

建堆的复杂度是O(N)
向下调整的复杂度是O(logN)，是以2为底数的对数。

所以时间复杂度就是O(N*logN)，算是排序中比较快的算法了。

4.2 TopK问题

4.2.1思路

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

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于这种问题，一般会想到使用排序，但是数据量非常大的情况下，排序不太可取，因为数据可能不能一下子加载到内存中。最佳的方法还是用堆来解决：

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

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

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

比如，要找前k个最大的元素，我们建k个元素的小堆，只要剩下的元素的值比堆顶元素大，就与堆顶元素发生交换，并使用向下调整算法，这样子在堆顶的元素一定是最小的，在堆顶的元素如果不是前k个最大元素，就会被剩下的元素中出现的前k个最大元素所替代，这样子就可以解决TopK问题了。

大家需要注意的是，当堆排序排升序的时候需要建大堆，而TopK问题找前k个最大的元素是建小堆。两者不一样。

4.2.2 代码实现

我们先要创建一个文件，并随机生成十万个数据。这里需要用到srand函数，并传入时间戳time。并写入文件中。

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

void CreateDate()
{
	int num = 100000;
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("File: fin open fail");
		exit(-1);
	}
    //时间戳的随机数
	srand(time(0));
	for (int i = 0; i < num; i++)
	{	//生成0~999999的数
		fprintf(fin, "%d\n", (rand() + i) % 1000000);
	}
	
	fclose(fin);
}

以只读的方式打开文件，然后动态开辟一个k个大小的数组。将前k个元素赋值到数组中，使用向下调整算建小堆。之后用while循环读取剩下元素，比堆顶大的元素，与其进行交换，再向下调整，直到结束。

void TopK()
{
	printf("请输入k:>");
	int k = 0;
	scanf("%d", &k);

	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}

	//新建一个数组
	int* arr = (int*)malloc(sizeof(int) * k);
	if (arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//读取k个数据到新建的堆中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &arr[i]);
	}

	//建小堆，向下调整
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, k, i);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		//比较另外的N-K个数与堆顶的大小
		if (x > arr[0])
		{
			arr[0] = x;
			AdjustDown(arr, k, 0);
		}
	}

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

	fclose(fout);
}

int main()
{
	CreateDate();
	TopK();

	return 0;