【数据结构入门】堆（Heap）_堆数据结构

一、堆的结构及实现（重要）

1.1 二叉树的顺序结构

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

---

1.2 堆的概念及结构

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。堆总是满足下列性质：

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

堆是非线性数据结构，相当于一维数组，有两个直接后继。

【大根堆和小根堆】：

根结点最大的堆叫做大根堆，树中所有父亲都大于或等于孩子。

根结点最小的堆叫做小根堆，树中所有父亲都小于或等于孩子。

【思考】这个大根堆和小根堆有什么特点呢？

最值总在 0 号位，根据这个特点我们就可以做很多事情，比如TopK问题 (在一堆数据里面找到前 K 个最大 / 最小的数)，生活中也有很多实例，比如点餐软件中有上千家店铺，我想选出该地区好评最多的十家川菜店，我们不用对所有数据排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。

---

1.3 堆的实现

1.3.1 堆的向下调整算法

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

int array[] = { 27,15,19,18,28,34,65,49,25,37 }; // 根节点的左右子树都是小堆
1

上面的数组，因为根节点的左右子树都是小堆，所以我们从根节点开始调整，将其调成小堆。

向下调整算法思路（调成小堆）：

• 从根节点开始，不断往下调。
• 选出根节点的左右孩子中「最小的孩子」，与「父亲」进行比较。
• (1) 如果父亲小于孩子，就不需处理了，整个树已经是小堆了。
• (2) 如果父亲大于孩子，就跟父亲交换位置，并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。

向下调整算法过程演示（调成小堆，把大的节点往下调整）：

向下调整算法代码：

// 向下调整算法，建小堆，把大的节点往下调整
// 前提是：左右子树都是小堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默认左孩子最小
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 1. 选出左右孩子最小的那个，先判断右孩子是否存在
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++; // 指向右孩子
		}

		// 2. 最小的孩子与父亲比较
		if (a[parent] > a[child]) // 如果父亲大于孩子
		{
			// 父亲与孩子交换位置
			Swap(&a[parent], &a[child]);

			// 更新父子下标，原先最小的孩子作为父亲，继续往下调
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父亲小于孩子，说明已经为小堆了，停止调整
		{
			break;
		}
	}
}
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

---

1.3.2 向下调整算法的时间复杂度

我们以满二叉树计算，最坏情况下，向下调整算法最多进行满二叉树的高度减1次比较，则说明向下调整算法最多调整满二叉树的高度减1次，n 个节点的满二叉树高度为 log₂(n+1)，估算后所以时间复杂度为 O(log₂n)。

---

1.3.3 堆的创建（向下调整）

下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆，我们需要通过算法把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆，我们应该怎么调整呢？

我们倒着调整，从下到上，从「倒数第一个非叶子节点的子树」开始，依次遍历完所有非叶子节点，分别对每个子树进行「向下调整」成 (大 / 小) 堆，一直调整到「根节点」，就可以建成一个 (大 / 小) 堆。

为什么要倒着调整呢？因为这样我们可以把「倒数第一个非叶子节点的子树」的左右子树看成是一个 (大 / 小) 堆，此时才能去使用向下调整算法。比如下图中的黄色填充的子树，3 的左子树 6 就可以看成是一个大堆。

【实例】：将下面的数组建成一个大堆

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

​

建堆过程演示（以建大堆为例）：从下到上，依次遍历完所有非叶子节点，分别对每个子树进行向下调整。

依次对 每一步 中，方框内的树 进行 向下调整 为一个 大堆。

建堆代码：

// 交换函数
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// 向下调整算法，建大堆，把小的节点往下调
// 前提是：左右子树都是大堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默认左孩子最大
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 1. 选出左右孩子最大的那个，先判断右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 指向右孩子
		}

		// 2. 最大的孩子与父亲比较
		if (a[parent] < a[child]) // 如果父亲小于孩子
		{
			// 父亲与孩子交换位置
			Swap(&a[parent], &a[child]);

			// 更新父子下标，原先最大的孩子作为父亲，继续往下调
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父亲大于孩子，说明已经为大堆了，停止调整
		{
			break;
		}
	}
}

void HeapSort(int* a, int size)
{
    /* 建堆（大堆）
    * 倒着调整，从倒数第一个非叶子节点的子树进行向下调整，直到调整到根节点的树
    */
	int parent = ((size - 1) - 1) / 2; // 最后一个叶子节点的父亲的下标
	for (int i = parent; i >= 0; i--)  // 从下到上，依次遍历完所有子树，分别对其进行调整
	{
		AdjustDown(a, size, i);
	}
    /* 堆排序
    * 排升序 --> 建大堆，每次选出一个最大的数放到最后
    * 排降序 --> 建小堆，每次选出一个最小的数放到最后
    */
    // 下面是排升序：
	int end = size - 1; // 记录堆中最后一个元素的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);  // 将堆顶元素和堆中最后一个元素交换，把最大的数(堆顶)放到最后
		AdjustDown(a, end, 0); // 不看最后一个数，从根节点开始，对前面的数进行向下调整成大堆
		end--;
	}
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

---

1.3.4 堆排序

排升序 --> 建大堆：

1. 【思考】排升序，建小堆可以吗？-- 可以是可以，但没啥意思。
   首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第2小的数，不断重复上述过程……。建 n 个数的堆时间复杂度是O(N)，所以上述操作时间复杂度为O(N²)，效率太低，尤其是当数据量大的时候，效率更低，同时堆的价值没有被体现出来，还不如用直接排序。

2. 【最佳方法】排升序，因为数字越来越大，需要找到最大的数字，得建大堆

   1. 首先对 n 个数建大堆。
   2. 将最大的数（堆顶）和最后一个数交换，把最大的数放到最后。
   3. 前面 n-1 个数的堆结构没有被破坏（最后一个数不看做堆里面的），根节点的左右子树依旧是大堆，所以我们进行一次向下调整成大堆即可选出第2大的数，放到倒数第二个位置，然后重复上述步骤……。

3. 【时间复杂度】：建堆时间复杂度为O(N)，向下调整时间复杂度为O(log₂N)，这里我们最多进行N-2次向下调整，所以堆排序时间复杂度为O(N*log₂N)，效率是很高的。

​

排降序 --> 建小堆：

【最佳方法】排降序，因为数字越来越小，需要找到最小的数字，得建小堆

1. 首先对 n 个数建小堆。
2. 将最小的数（堆顶）和最后一个数交换，把最小的数放到最后。
3. 前面 n-1 个数的堆结构没有被破坏（最后一个数不看做堆里面的），根节点的左右子树依旧是小堆，所以我们进行一次向下调整成小堆即可选出第2小的数，放到倒数第二个位置，然后重复上述步骤……。
4. 【时间复杂度】：建堆时间复杂度为O(N)，向下调整时间复杂度为O(log₂N)，这里我们最多进行N-2次向下调整，所以堆排序时间复杂度为O(N*log₂N)，效率是很高的。

---

1.3.5 建堆的时间复杂度

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

建堆要从倒数第一个非叶子节点开始调整，也即是从倒数第二层开始调，可得出时间复杂度公式：
$$T(n)=\sum (每层节点数\ast (堆的高度-当前层数))$$

所以，建堆的时间复杂度为O(N)。

---

【上面学了那么多，这里小小总结一下】

1. 堆的向下调整算法就是，在该节点左右子树都是一个小/大堆的前提下，将以该节点为根的树调整成一个小/大堆。
2. 堆的创建就是倒着调整，从下到上，从倒数第一个非叶子节点的子树开始，依次遍历完所有子树，分别对其进行向下调整。
3. 时间复杂度：堆的向下调整算法为O(log₂N)，堆的创建为O(N)。

---

二、堆的相关接口实现（以大堆为例）

首先新建一个工程（ 博主使用的是 VS2019 ）

• Heap.h（堆的类型定义、接口函数声明、引用的头文件）
• Heap.c（堆接口函数的实现）
• Test.c（主函数、测试堆各个接口功能）

Heap.h 头文件代码如下：

#pragma once

#include<stdio.h>   // printf, perror
#include<stdbool.h> // bool
#include<assert.h>  // assert
#include<stdlib.h>  // malloc, free
#include<string.h>  // memcpy

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a; // 指向动态开辟的数组
	int size;      // 数组中有效元素个数
	int capacity;  // d容量
}Heap;

// 交换函数
void Swap(HPDataType* a, HPDataType* b);
// 向下调整函数（调成大堆，把小的往下调）
void AdjustDown(HPDataType* a, int size, int parent);
// 向上调整函数（调成大堆，把大的往上调）
void AdjustUp(HPDataType* a, int child);

// 初始化堆
void HeapInit(Heap* php, HPDataType* arr, int n);
// 销毁堆
void HeapDestroy(Heap* php);
// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x);
// 删除堆顶元素，删除后保持它依然是堆
void HeapPop(Heap* php);
// 获取堆顶元素，也即是最值
HPDataType HeapTop(Heap* php);
// 判断堆是否为空，为空返回true，不为空返回false
bool HeapEmpty(Heap* php);
// 获取堆中有效元素个数
int HeapSize(Heap* php);
// 打印堆
void HeapPrint(Heap* php);
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
38
39

---

2.1 堆的初始化

堆的初始化，首先需要实现一个向下调整算法：

// 交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

// 向下调整算法（调成大堆，把小的往下调）
void AdjustDown(HPDataType* a, int size, int parent)
{
	// 左孩子下标，初始默认左孩子最大
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 选出左右孩子最大的那个，先判断右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 右孩子最大
		}
		// 最大的孩子与父亲比较
		if (a[parent] < a[child]) // 如果父亲小于孩子
		{
			// 父亲与孩子交换位置
			Swap(&a[parent], &a[child]);

			// 更新父子下标，原先最大的孩子作为父亲，继续往下调
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父亲大于孩子，说明已经为大堆了，停止调整
		{
			break;
		}
	}
}
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

堆的初始化代码：

// 初始化堆，用一个给定的数组来初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
	assert(php); // 断言
	
	// 动态开辟n个空间
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	// 把给定数组的各元素值拷贝过去
	memcpy(php->a, arr, sizeof(HPDataType) * n);
	php->size = php->capacity = n;

	// 建堆(建大堆）
	int parent = ((php->size - 1) - 1) / 2; // 倒数第一个非叶子节点下标
	for (int i = parent; i >= 0; i--) // 从下到上，依次遍历完所有子树，分别对其进行调整
	{
		AdjustDown(php->a, php->size, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

2.2 堆的销毁

// 销毁堆
void HeapDestroy(Heap* php)
{
	assert(php);

	free(php->a); // 释放动态开辟的空间
	php->a = NULL;
	php->size = php->capacity = 0;
}
1
2
3
4
5
6
7
8
9

---

2.3 堆的插入

先插入一个新元素到数组的尾上，从插入的新元素开始，进行向上调整算法，直到满足（大/小）堆。

堆的插入过程演示：

堆的插入，首先需要实现一个向上调整算法：

// 向上调整算法（调成大堆，把大的往上调）
void AdjustUp(HPDataType* a, int child)
{
	// 父节点的下标
	int parent = (child - 1) / 2;

	//while (parent >= 0) parent不会小于0
	while (child > 0)
	{
		// 孩子与父亲进行比较
		if (a[child] > a[parent]) // 如果孩子大于父亲
		{
			// 孩子与父亲交换
			Swap(&a[child], &a[parent]);

			// 更新父子下标，原先父亲作为孩子，继续往上调
			child = parent;
			parent = (child - 1) / 2;
		}
		else // 如果孩子小于父亲，说明已经为大堆了，停止调整
		{
			break;
		}
	}
}
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

堆的插入代码：

// 插入元素（插入到堆的末尾），插入后并保持它依然是堆
void HeapPush(Heap* php, int x)
{
	assert(php);

	// 先检查空间是否已满
	if (php->capacity == php->size)
	{
		// 增容两倍
		php->capacity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);
		if (tmp != NULL)
		{
			php->a = tmp;
			tmp = NULL;
		}
	}

	// 插入元素
	php->a[php->size] = x;
	php->size++;

	// 从插入的元素开始，进行向上调整，保持它依然是堆
	AdjustUp(php->a, php->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

---

2.4 堆的删除

1. 将堆顶元素和最后一个元素交换（这样就变成尾删了，很方便）
2. 删除堆中最后一个元素
3. 从根节点开始，对剩下元素进行向下调整，调成（大/小）堆

堆的删除过程演示：

堆的插入，首先需要实现一个向下调整算法：前面已经实现过了，这里就不展示了。

堆的删除代码：

// 删除堆顶元素，删除后保持它依然是堆
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能为空

	// 将堆顶元素和最后一个元素交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	// 删除堆中最后一个元素
	php->size--;

	// 从根节点开始，对剩下元素进行向下调整成大堆，保持它依然是堆
	AdjustDown(php->a, php->size, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

2.5 获取堆顶元素

// 获取堆顶元素，也即是最值
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php)); // 堆不能为空

	return php->a[0];
}
1
2
3
4
5
6
7
8

---

2.6 堆的判空

// 判断堆是否为空，为空返回true，不为空返回false
bool HeapEmpty(Heap* php)
{
	assert(php);

	return php->size == 0;
}
1
2
3
4
5
6
7

---

2.7 拓展1：找出堆中前k个最大元素

堆的相关接口实现好了，因为是大堆，所以我们可以很方便的来找出堆中前 k 个最大元素。

这里要和前面的堆排序区分开哦，这里我们并不是在堆中对所有元素排好序。

void TestHeap()
{
	int a[] = { 1,5,3,8,7,6 };

	Heap hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(a[0])); // 初始化堆

	int k = 0;
	scanf("%d", &k);

	printf("找出堆中前%d个最大元素：\n", k);
	while (!HeapEmpty(&hp) && k--)
	{
		printf("%d ", HeapTop(&hp)); // 获取堆顶元素
		HeapPop(&hp); // 删除堆顶元素
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

---

2.8 拓展2：堆的创建（向上调整）

下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆，我们需要通过「向上调整算法」把它构建成一个堆。如果根节点左右子树不是一个 (大 / 小) 堆，我们应该怎么调整呢？

我们从上到下，从「第一个节点（也就是根节点）的左孩子」开始，依次遍历完所有节点，分别对每个节点进行「向上调整」，一直到「最后一个节点」，就可以建成一个 (大 / 小) 堆。

我们把数组中的「第一个元素」看作是一个「堆」，剩余的元素依次插入到这个「堆」中。前面我们也实现了堆的插入接口，原理就是向上调整。

// 向上调整算法建堆
void CreateHeap(int* a, int size)
{
	// 把第一个元素看作是堆，剩余的元素依次插入堆中
	for (int i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}
}
1
2
3
4
5
6
7
8
9

---