【数据结构】二叉树顺序存储：堆详解！(图解+源码)

🎥 屿小夏 ： 个人主页 🔥个人专栏 ： 数据结构解析 🌄 莫道桑榆晚，为霞尚满天！

🌤️前言

堆是一种基本而强大的数据结构。本文将深入探讨堆的概念、原理以及实现。

🌤️堆的理论

☁️二叉树的顺序存储

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

☁️堆的概念

堆的性质：

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

🌤️堆的实现逻辑

☁️堆向下调整算法

一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整
成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

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

☁️建堆

给定一个数组,这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，这个时候就需要我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆(向下调整)。

int a[] = {1,5,3,8,7,6};
1

☁️建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

根据上图可以推算出: 建堆的时间复杂度为O(N)。

☁️堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

☁️堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

🌤️堆的代码是实现

☁️堆的结构体

typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* a;
	int size;  //有效元素
	int cpciti; //容量
}HP;
1
2
3
4
5
6
7
8

• HeapDataType 定义了堆中元素的数据类型，这里是整数。
• struct Heap 定义了一个包含堆数据的结构体，包括一个指向堆数组的指针 ，堆的有效元素个数 ，以及堆的容量 。

☁️堆的初始化

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->cpciti = 0;
}
1
2
3
4
5
6

首先使用 断言来确保传入的指针 不为空。然后，将堆数组指针设置为 NULL，将堆的有效元素个数和容量都初始化为 0。

☁️堆的销毁

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->cpciti = 0;
}
1
2
3
4
5
6
7

使用 断言确保传入的指针 不为空。然后，使用函数释放堆数组分配的内存，并将指针设置为 NULL。最后，将堆的有效元素个数和容量都设置为 0。

☁️堆的插入

void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(HP* hp, HeapDataType x)
{
	assert(hp);
	//
	if (hp->size == hp->cpciti)
	{
		int newCapacity = hp->cpciti == 0 ? 4 : hp->cpciti * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->cpciti = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

AdjustUp用于将堆的最后一个节点（即插入的新节点）向上调整，使得以新节点为叶子节点的子树仍然满足堆的性质。具体步骤如下：

1. 初始化parent为(child - 1) / 2，即新节点的父节点。
2. 如果child大于0（即child不是根节点），则执行以下操作：
   • 如果child节点的值小于parent节点的值，则交换child和parent节点的值，并更新child为parent，parent为(child - 1) / 2。
   • 否则，跳出循环。
3. 调整结束。

HeapPush用于向堆中插入一个新的元素。具体步骤如下：

1. 检查堆的大小是否达到了容量上限，如果是，则进行扩容操作。
2. 将新元素x放入堆的最后一个位置。
3. 堆的大小加1。
4. 调用AdjustUp函数，将新插入的元素向上调整。

☁️堆的删除

void AdjustDown(HeapDataType* 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 HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

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

	AdjustDown(hp->a,hp->size,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

AdjustDown用于将堆的根节点向下调整，使得以根节点为根的子树仍然满足堆的性质。具体步骤如下：

1. 初始化child为parent的左孩子节点。
2. 如果child小于n（即child在数组范围内），则执行以下操作：
   • 如果child+1也小于n且右孩子节点的值小于左孩子节点的值，则将child更新为右孩子节点。
   • 如果child节点的值小于parent节点的值，则交换child和parent节点的值，并更新parent为child，child为parent的左孩子节点。
   • 否则，跳出循环。
3. 调整结束。

HeapPop用于删除堆的根节点。具体步骤如下：

1. 交换根节点和最后一个节点的值。
2. 将堆的大小减1。
3. 调用AdjustDown函数，将根节点向下调整。

☁️取堆顶数据

HeapDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}
1
2
3
4
5
6

断言来确保传入的指针 是非空的（不为 NULL），以及堆的大小大于0。如果这些条件不满足，程序会终止执行。然后，返回堆的顶部元素，也就是堆数组中的第一个元素。

☁️堆的数据个数

int HeapSize(HP* hp)
{
	return hp->size;
}
1
2
3
4

size即堆的大小，表示堆中当前包含的元素个数。

☁️堆的判空

int HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}
1
2
3
4
5

断言确保传入的指针不为空，检查堆的大小是否等于0。如果堆的大小为0，函数返回1（表示堆为空），否则返回0（表示堆不为空）。

🌤️堆特性总结

1. 堆是一棵完全二叉树，即除了最后一层外，其他层都是满的，最后一层从左到右填满。
2. 堆分为大根堆和小根堆两种，大根堆中每个节点的值都大于其子节点的值，小根堆中每个节点的值都小于其子节点的值。
3. 堆的根节点是堆中的最小（或最大）元素。
4. 堆中的任意节点的值都小于（或大于）其子节点的值。
5. 堆中的元素是按照层序遍历的顺序存储在数组中的，可以用数组来实现堆。
6. 堆的插入和删除操作分别为向上调整（AdjustUp）和向下调整（AdjustDown），保证插入和删除后仍然满足堆的性质。
7. 堆的时间复杂度为O(logN)，其中N为堆中元素的个数。

🌤️全篇总结

堆作为数据结构中的重要部分，展现了在多种算法和应用中的价值。掌握堆的知识会对你以后解决各种问题和优化性能提供重要帮助。