C/C++数据结构(八) —— 二叉堆

导读:本篇文章讲解 C/C++数据结构(八) —— 二叉堆,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

在这里插入图片描述


什么是二叉堆

⼆叉堆本质上是⼀种 完全⼆叉树,它分为两个类型,最大堆最小堆

🍑 最大堆

什么是最⼤堆呢?

最⼤堆的任何⼀个⽗节点的值,都 ⼤于等于 它左、右孩⼦节点的值(如下图所示👇)。

在这里插入图片描述

🍑 最小堆

什么是最⼩堆呢?

最⼩堆的任何⼀个⽗节点的值,都 ⼩于等于 它左、右孩⼦节点的值(如下图所示👇)。
在这里插入图片描述

🍑 堆顶

⼆叉堆的根节点叫作 堆顶

最⼤堆和最⼩堆的特点决定了:

1)最⼤堆的堆顶是整个堆中的 最⼤元素
 
2)最⼩堆的堆顶是整个堆中的 最⼩元素

🍑 堆的性质

性质:

堆中某个节点的值总是不大于或不小于其父节点的值;
 
堆总是一棵完全二叉树。

堆的结构

大根堆示例(如下图所示👇
在这里插入图片描述

小根堆示例(如下图所示👇
在这里插入图片描述

堆的要点

在实现堆的代码之前,我们还需要明确⼀点:⼆叉堆虽然是⼀个完全⼆叉树,但它的存储⽅式并不是链式存储,⽽是 顺序存储

换句话说,⼆叉堆的所有节点都存储在数组中如下图所示👇)。
在这里插入图片描述

在数组中,在没有左、右指针的情况下,如何定位⼀个⽗节点的左孩⼦和右孩⼦呢?

像上图那样,可以依靠数组下标来计算。

假 设 ⽗ 节 点 的 下 标 是 parent
 
那 么 它 的 左 孩 ⼦ 下 标 就 是

2

×

p

a

r

e

n

t

+

1

2×parent+1

2×parent+1
 
右 孩 ⼦ 下 标 就 是

2

×

p

a

r

e

n

t

+

2

2×parent+2

2×parent+2

例如上⾯的例⼦中,节点 6 包含 910 两个孩⼦节点,节点 6 在数组中的下标是 3,节点 9 在数组中的下标是 7,节点 10 在数组中的下标是 8那么

7

=

3

×

2

+

1

7 = 3×2+1

7=3×2+1
 

8

=

3

×

2

+

2

8 = 3×2+2

8=3×2+2

1. 初始化堆

首先,创建一个堆的类型,该类型中需包含堆的基本信息:存储数据的数组堆中元素的个数 以及 当前堆的最大容量。

📝 代码示例

typedef int HPDataType; //堆中存储数据的类型

typedef struct Heap
{
	HPDataType* a; //用于存储数据的数组
	int size; //记录堆中已有元素个数
	int capacity; //记录堆的容量
}HP;

然后我们需要一个初始化函数,对刚创建的堆进行初始化。

📝 代码示例

// 堆的初始化
void HeapInit(HP* php) {
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

2. 打印堆

打印堆中的数据,按照堆的物理结构进行打印,即打印为一组连续的数字。

📝 代码示例


// 堆的打印
void HeapPrint(HP* php) {
	assert(php);

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

3. 堆的插入

当⼆叉堆插⼊节点时,插⼊位置是完全⼆叉树的最后⼀个位置。

例如插⼊⼀个新节点,值是 0如下图所示👇)。
在这里插入图片描述

这时,新节点的⽗节点 50 ⼤,显然不符合 最⼩堆 的性质。于是让新节点 “上浮”,和⽗节点交换位置(如下图所示👇)。
在这里插入图片描述

继续⽤节点 0 和⽗节点 3 做⽐较,因为 0 ⼩于 3,则让新节点继续 “上浮”如下图所示👇)。
在这里插入图片描述

继续⽐较,最终新节点 0 “上浮” 到了堆顶位置(如下图所示👇)。
在这里插入图片描述

这种方法叫做 堆的向上调整算法

🍑 堆的向上调整算法

在对二叉堆进行 插入数据 时,要使用 向上调整 算法,它既可以构建 大堆,也可以构建 小堆

核心思想(以构建小堆为例):

1)将目标结点与其父结点比较。
 
2)若目标结点的值比其父结点的值小,则交换目标结点与其父结点的位置,并将原目标结点的父结点当作新的目标结点继续进行向上调整。
 
3)若目标结点的值比其父结点的值大,则停止向上调整,此时该树已经是小堆了。

🍅 向上调整构建小堆

假设有下面这样一直数据,我们先构建一个小堆出来。

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

动图演示👇(我这里用的负数,实际上大家看动图的时候,默认不看负号)

在这里插入图片描述

然后我们在末尾插入一个比堆顶 15 还要小的数字 2动图演示👇)。

在这里插入图片描述

注意:

这里再解释一下为什么都是负数?
 
因为动图上的二叉堆只有大堆,所以我就添加了一个负号,大家看动图的时候,不要看负号

📝 代码示例

//交换变量
void Swap(HPDataType* pa, HPDataType* pb) {
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//向上调整 --> 建小堆
void AdjustUp1(HPDataType* 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; // 已经是小堆了,直接跳出循环
		}
	}
}

🍅 向上调整构建大堆

还是下面这样一直数据,我们先构建一个大堆出来。

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

动图演示👇

在这里插入图片描述

然后我们在末尾插入一个比堆顶 65 还要大的数字 99动图演示👇)。

在这里插入图片描述

📝 代码示例

//交换变量
void Swap(HPDataType* pa, HPDataType* pb) {
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//向上调整 --> 建大堆
void AdjustUp2(HPDataType* 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; // 已经是大堆了,直接跳出循环
		}
	}
}

有没有发现,其实构建大堆只是把上面构建小堆中 if 语句中的 小于 改成了 大于

🍑 插入实现

既然 插入 是向上调整,那我们直接用刚刚写好的函数就好了,这里以构建 小堆 为例。

📝 代码示例

// 堆的插入
void HeapPush(HP* php, HPDataType x) {
	assert(php);

	if (php->size == php->capacity) {
		int newCapacity = php->capacity == (0) ? (4) : (php->capacity * 2);

		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;
	
	//创建小堆
	AdjustUp1(php->a, php->size - 1);
}

4. 堆的删除

⼆叉堆删除节点的过程和插⼊节点的过程正好相反,所删除的是处于堆顶的节点。

例如删除 最⼩堆 的堆顶节点 1如下图所示👇)。
在这里插入图片描述

这时,为了继续维持完全⼆叉树的结构,我们把堆的最后⼀个节点 10 临时补到原本堆顶的位置(如下图所示👇)。
在这里插入图片描述

接下来,让暂处堆顶位置的节点 10 和它的左、右孩⼦进⾏⽐较,如果左、右孩⼦节点中最⼩的⼀个(显然是节点 2 )⽐节点 10 ⼩,那么让节点 10 “下沉”如下图所示👇)。
在这里插入图片描述

继续让节点 10 和它的左、右孩⼦做⽐较,左、右孩⼦中最⼩的是节点 7,由于 10 ⼤于 7,让节点 10 继续 “下沉”如下图所示👇)。
在这里插入图片描述

这种方法叫 堆的向下调整算法

🍑 堆的向下调整算法

那么这个 堆的向下调整算法堆的向上调整算法 有什么关联呢?

首先若想将其调整为小堆,那么根结点的左右子树必须都为小堆。
 
若想将其调整为大堆,那么根结点的左右子树必须都为大堆。

也就是说:

如果我们使用 向上调整算法 构建了一个 小堆,那么 向下调整算法 也必须只能调整 小堆
 
如果我们使用 向上调整算法 构建了一个 大堆,那么 向下调整算法 也必须只能调整 大堆

核心思想(以调整小堆为例):

1)从根结点处开始,选出左右孩子中值较小的孩子。
 
2)让小的孩子与其父亲进行比较。
 
3)若小的孩子比父亲还小,则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整,直到调整到叶子结点为止。
 
4)若小的孩子比父亲大,则不需处理了,调整完成,整个树已经是小堆了。

🍅 向下调整小堆

假设有下面这样一直数据,我们先构建一个小堆出来。

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

动图演示👇

在这里插入图片描述

然后我们删除堆顶的元素 15动图演示👇)。

在这里插入图片描述

📝 代码示例

//交换变量
void Swap(HPDataType* pa, HPDataType* pb) {
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

// 向下调整 --> 调小堆
void AdjustDown1(HPDataType* a, int size, int root) {
	int parent = root;

	//child记录的是左右孩子中值较小的孩子的下标
	int child = parent * 2 + 1; // 首先默认child为左孩子,并且是左右当中最小的孩子
	while (child < size) {
		//1、选出左右孩子中小的那个
		//在孩子存在的前提下,如果右孩子比 【默认的左孩子】 还要小,那么就把 child+1 指向右孩子;
		//如果右孩子比左孩子大,那么就不进入if语句
		if (child + 1 < size && a[child + 1] < a[child]) { //左孩子的下标加1,就是右孩子
			++child;
		}

		//2、如果孩子小于父亲,则交换,并继续往下调整
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

🍅 向下调整大堆

还是下面这样一直数据,我们先构建一个大堆出来。

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

动图演示👇

在这里插入图片描述

然后我们删除堆顶的元素 65动图演示👇)。

在这里插入图片描述

📝 代码示例

//交换变量
void Swap(HPDataType* pa, HPDataType* pb) {
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

// 向下调整 --> 调大堆
void AdjustDown2(HPDataType* a, int size, int root) {
	int parent = root;

	//child记录的是左右孩子中值较大的孩子的下标
	int child = parent * 2 + 1; // 首先默认child为左孩子,并且是左右当中最大的孩子
	while (child < size) {
		//1、选出左右孩子中较大的那个孩子
		//在孩子存在的前提下,如果右孩子比 【默认的左孩子】 还要大,那么就把 child+1 指向右孩子;
		//如果右孩子比左孩子小,那么就不进入if语句
		if (child + 1 < size && a[child + 1] > a[child]) { //左孩子的下标加1,就是右孩子
			++child;
		}

		//2、如果孩子大于父亲,则交换,并继续往下调整
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

🍑 删除实现

既然 删除向下调整,那我们直接用刚刚写好的函数就好了。

上面的 插入 是构建的小堆,所以这里删除调整的应该也必须是 小堆

📝 代码示例

// 堆的删除
void HeapPop(HP* php) {
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]); //把堆顶的数据和最后一个位置的数据互换
	php->size--; //删除最后一个节点(也就是删除原来堆顶的元素)

	//向下调整(调小堆)
	AdjustDown1(php->a, php->size, 0); 
}

5. 获取堆顶的数据

获取堆顶的数据,即返回数组下标为 0 的数据。

📝 代码示例

// 取堆顶的数据
HPDataType HeapTop(HP* php) {
	assert(php);
	assert(php->size > 0);

	return php->a[0]; //返回堆顶数据
}

6. 获取堆的数据个数

获取堆的数据个数,即返回堆结构体中的 size 变量。

📝 代码示例

// 堆的数据个数
int HeapSize(HP* php) {
	assert(php);

	return php->size; //返回堆中数据个数
}

7. 堆的判空

堆的判空,即判断堆结构体中的 size 变量是否为 0

📝 代码示例

// 堆的判空
bool HeapEmpty(HP* php) {
	assert(php);
	
	//如果size等于0就为空,不等于0就不为空
	return php->size == 0;
}

8. 堆的销毁

为了避免内存泄漏,使用完动态开辟的内存空间后都要及时释放该空间。

📝 代码示例

// 堆的销毁
void HeapDestory(HP* php) {
	assert(php);

	free(php->a); //释放动态开辟的数组
	php->a = NULL; //及时置空
	php->size = php->capacity = 0; //元素个数和容量置为0
}

9. 总结

复杂度分析:

堆的插⼊操作是单⼀节点的 “上浮”,堆的删除操作是单⼀节点的 “下沉”,这两个操作的平均交换次数都是堆⾼度的⼀半,所以时间复杂度是

O

(

l

o

g

N

)

O(logN)

O(logN)
 
而构建堆的时间复杂度是

O

(

N

)

O(N)

O(N)

堆的应用:

⼆叉堆是实现 堆排序优先队列 的基础。
 
关于这两者,我会在后续的文章中详细介绍。

接口函数贴图

最后附上一张完整的 二叉堆接口函数图
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/80853.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!