初阶数据结构之---二叉树的顺序结构-堆

引言

今天要讲的堆，不是操作系统虚拟进程地址空间中（malloc，realloc等开空间的位置）的那个堆，而是数据结构中的堆，它们虽然名字相同，却是截然不同的两个概念。堆的底层其实是完全二叉树，如果你问我，完全二叉树是什么。好吧，那我先从树开始讲起，开始我们今天的内容。

树是什么？

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。

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

上图的三个结构都不是树，不符合子树之间无交集的定义，子树相交其实就成了图。

关于树的常见概念

1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
2. 叶节点/终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
4. 双亲节点/父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
5. 孩子节点/子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点树的高度/深度：树中节点的最大层次； 如上图：树的高度为4
6. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
7. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。

以上是学习堆要了解的基本概念。

对于树结构的模拟

虽然树已经有了很多限制和规则，但其还是有着很大的灵活性，我们根据其结构特性也给出了一些定义方案。

1.如果明确了树的度，那么可以定义TreeNode

typedef struct TreeNode
{
	int data;
	struct TreeNode* child1;
	struct TreeNode* child2;
	struct TreeNode* child3;
	//。。。
}TreeNode;

像上述代码中定义的那样，可以固定定义一种固定度数的结点。

2.左孩子右兄弟表示法

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

实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

但我们用的正真多的，是二叉树

二叉树是什么？

二叉树的概念

二叉树是特殊的树

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

上图中我们可以看出：

1. 二叉树的度不大于2（每个结点最多有两个孩子）

2. 二叉树有左右之分，次序不能颠倒因此二叉树是有序树

当然，以下几种情况也符合二叉树的定义，都是二叉树

二叉树的存储结构

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

1.顺序存储

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

2.链式存储

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

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

特殊的二叉树

1. 满二叉树：一个二叉树的每一层都是满的，如果一个树的层数为K，且结点数为2^k - 1，则它就是满二叉树。

2.完全二叉树：如一个树的深度为h，前h-1层都是满的，最后一层不满但连续。

下图中，左边的是满二叉树，右边的是完全二叉树

• 完全二叉树是一种效率很高的数据结构，堆的逻辑结构实则就是一个完全二叉树。

二叉树顺序结构实现（堆）

普通的二叉树（我们可以称为非完全二叉树）是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

如果强行用堆表示普通的二叉树，就会像下面这样：

如果用完全二叉树实现，那么就是这样：

现在应该能体会到两种实现的区别了吧

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

堆的性质：

• 一颗完全二叉树
• 大堆：树中任何一个父亲都大于等于孩子
• 小堆：树中任何一个父亲都小于等于孩子

在这个堆中，如果你细心观察，可以发现如下规律（这个规律很重要）：

知道父亲下标（parent）找孩子（child）：

• 左孩子下标（leftchild）=  parent * 2 + 1
• 右孩子下标（rightchild）=  parent * 2 + 2

知道孩子下标（child）找父亲（parent）：

• parent  =（child - 1）/  2

用代码模拟堆的结构，就是以下这样

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//存放堆数据的数组
	int _size;//堆数据个数
	int _capacity;//堆的容量-可扩容
}Heap;

下面我们默认先建一个小堆，后期如果需要改大堆只需要变动相应比较符号就可以

堆的插入

如果存在一个有十个元素的堆，想要往其中插入一个新的元素，其过程是下面这样

以下是插入部分的代码实现

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
    //如果空间不够就扩容
	if (hp->_size == hp->_capacity) {
		int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL) {
			perror("realloc fail:");
			exit(1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
    //向上调整算法
    AdjustUp(hp->_a, hp->_size - 1);
}

在这里，将新插入的10这个元素往上调整的过程，我们称之为向上调整，涉及到一个算法，那就是向上调整算法，现在我们来实现一份。

向上调整算法

在比较交换元素的过程中，我们提供一个比较函数以便交换元素

//交换
void my_swap(HPDataType* a, HPDataType* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

 以下就是对向上调整的实现

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
    //如果孩子为0则比较结束
	while (child > 0) {
		if (a[parent] > a[child]) {
			my_swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else break;
	}
}

1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点
2. 比较父子结点大小：如果建立小堆，且子节点小于父节点，交换父子结点数据；如果此时子节点大于父节点，跳出循环
3. 更新父子结点：将父节点的位置赋给child，同时更新parent
4. 检查是否退出循环：如果child==0时，跳出循环

堆的创建

下面我们给出一个数组的元素，建成一个堆。在刚刚讲完堆的插入和向上调整过后，其实创建堆就显得格外容易了。我们只需要从数组中取出元素，然后依次插入到堆中便可以完成堆的创建，以下是实现代码：

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
    //初始化堆时，别忘记初始化以下hp中的元素
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
	for (int i = 0; i < n; i++) {
		HeapPush(hp, a[i]);
		AdjustUp(hp->_a, hp->_size - 1);
	}
}

堆的删除

堆的删除，通常意义上是删除堆顶的元素。如果建的是小堆，那么堆顶的元素就是堆中最小的数；如果建的是大堆，那么堆顶就是堆中最大的元素。

想要删除堆顶元素，不能通过整体向前移动后面的堆元素的方式来删除元素，因为这样会打乱元素之间的父子关系，打乱了父子关系，整个堆就很有可能不符合“父亲一定小于等于（或大于等于）孩子”这一规则了。

真正的实现方式是，将堆顶元素和堆底元素互换位置，将size - 1，再将此时堆顶的元素进行向下调整。

过程见下图：

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size != 0);
	my_swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
    //向下调整
	AdjustDown(hp->_a, hp->_size, 0);
}

既然讲到了向下调整，其实就又涉及到了向下调整算法。

向下调整算法

向下调整，顾名思义就是将元素往下调，先给大家展示调整代码，再来解析过程

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child + 1] < a[child]) {
			child++;
		}
		if (a[parent] > a[child]) {
			my_swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}

1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点，这里先预设左孩子比右孩子小，当发现右孩子更小时，child + 1，在比较左右孩子之前，还需要考虑到child + 1不会导致越界
2. 比较父子结点：父节点大于子结点时（此时建立的是小堆），交换父子结点数据；如果父节点小于字结点，跳出循环
3. 更新父子结点：将child赋给parent，计算新的child，进入新一轮循环
4. 判断循环结束：当孩子跃出数据存储范围时，循环结束

取堆顶的数据

这里没什么好说，堆的数组中第一个元素就是堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size != 0);
	return hp->_a[0];
}

堆数据的个数和堆的判空

这里直接用堆中的size元素就OK

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

堆的销毁

跟顺序表的销毁基本一致

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = 0;
	hp->_size = 0;
}

到这里堆的实现基本上就结束了

体验一下手写的堆

#include"heap.h"
int main()
{
	Heap hp;
	int arr[] = { 5,4,3,2,1 };
	HeapCreate(&hp, arr, sizeof(arr) / sizeof(int));
	printf("%d\n\n", HeapSize(&hp));
	while (!HeapEmpty(&hp)) {
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

结语

今天的内容到这里就结束了，本篇博客带大家认识了一下树和堆，但这里只是带大家稍微看了看堆的实现。关于堆的内容其实还有很多，topk问题，堆排序，优先级队列中会更深入的带领大家去了解和使用堆，在下一篇数据结构中，会更深入的挖掘一些堆的应用，并计算一下其时间复杂度，让大家体会到堆的魅力。如果还想了解更多有趣的内容，还请多多支持博主，比心♥