（C语言）数据结构二叉树之堆

• （C语言）数据结构之二叉树——对于二叉树有不理解的老铁可以看一下这篇文章。

前言：二叉树的顺序结构

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

一、堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=K(2i+1) 且 Ki<=K(2i+2) (或Ki>=K(2i+1) 且Ki>=K (2i+2) ) i=1,2,…，则称为小堆（大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值（也就是说堆只分小根堆或者大根堆）
• 堆总是一棵完全二叉树。
  

二、堆的实现

我们怎么实现一个堆呢？先要知道两个核心算法分别是：堆的向下调整算法和堆的向上调整算法

1、堆向下调整算法

如下图：

简述一下就是从被调整的那个元素开始（这里假设被调整的元素是27），如果是小顶堆，27很明显比两个孩子都要大，那么就要跟两个孩子中最小的那个换（假如和19换的话就不符合小顶堆的特性），27换下去之后再与当前的两个孩子再比，跟最小的那个再换，直到换到最后一层或者不再比两个孩子大的时候就可以停止。

实现代码：
a是那个数组首元素的地址，n是数组中有效元素的个数，parent是要被调整的那个元素

void AdjustDown(HPDataType * a, int n, int parent)
//这里是以大顶堆向下调整的，若是小顶堆，要把下面的两个'>'换成'<'
{
	int minChild = parent * 2 + 1;//假设就把左孩子当作最小的那个
	while (minChild < n)//要小于当前数组总共的有效元素个数
	{
		// 找出大的那个孩子
		if (minChild + 1 < n && a[minChild + 1] > a[minChild])
		//minChild + 1 < n极端情况			
		{
			minChild++;
		}
		
		//找大的然后往上替换
		if (a[minChild] > a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
			//假设左孩子就是那个最小的，下一次循环进来能通过上一个if语句 进行调整
		}
		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

2、堆向上调整算法

如下图：

这里我们以最下层的10为例，以小堆的结构向上调整，10直接和双亲结点开始比较，将大的那个双亲结点换下来（因为双亲结点就是那个最大的或者最小的，换完之后不改变原来堆的结构），依次向上一层一层的换，直到10这个结点不再比双亲结点小，或者已经到了最顶端（下标为0）的时候就停止。
实现代码：
a是数组首元素的地址，child是要被修改的那个结点的下标

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)//已经到了最顶端（下标为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

3、堆的创建

下面我们随便给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？

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

选择向下调整？还是向上调整？ 答案是向下调整，为什么呢？ 原因有下面这几个
1、假设当前的完全二叉树是满二叉树，最后一层其实就占到总结点个数的一半，向上调整（除了）最上层的那一个结点，每个结点都要进行一次向上调整，而向下调整就反过来，直接省去了最下面一层的结点，从倒数的第一个非叶子节点的子树开始调整即可
2、以最坏的情况来看，层数越往下走，结点数越多，向上调整需要交换的次数就越多，而向下调整越下层的结点交换的次数反而越少。

基于上述原因我们这里采用向下调整才是最好的选择。我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

怎么求倒数第一个非叶子结点？

对于具有n个结点的完全二叉树，可以看着上图，按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 i 的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；若 i=0，那么i为根节点编号，则无双亲节点。
由于堆是一颗完全二叉树，就是它是从左到右依次排列，那么
倒数第一个非叶子节点=(最后一个结点的下标-1)/2

4、建堆的时间复杂度

因此：建堆的时间复杂度为O(N)。

5、堆的插入

先插入一个数据到数组的尾上，然后针对这一个元素进行向上调整算法，直到满足堆。
代码片段：

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// 扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	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

6、堆的删除

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

代码片段：

void HeapPop(HP* 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

7、堆的代码实现

函数接口如下：
这里我们结构体里的数组采用动态开辟的方式，所以创建一个HPDataType类型的指针。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;//有效元素个数
	int capacity;//当前数组的容量
}HP;

//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestory(HP* php);

//插入x继续保持堆形态
void HeapPush(HP* php, HPDataType x);

//删除堆顶元素
void HeapPop(HP* php);

//堆顶元素
HPDataType HeapTop(HP* php);
//判断堆空
bool HeapEmpty(HP* php);
//堆的元素个数
int HeapSize(HP* 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

完整代码链接

三、堆的应用

1、堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

• 建堆 （升序建大堆 ，降序建小堆）
• 利用堆删除思想来进行排序
  解释：由于堆的特殊特性堆顶元素一定是最大的或者最小的，让堆顶先与下标为n-1的元素交换，交换完再进行向下调整；让堆顶再与下标为n-2的元素交换，交换完再进行向下调整；让堆顶再与下标为n-3的元素交换，交换完再进行向下调整就这个过程循环往复，直到把下标为1的元素和下标为0的元素交换完成之后停止，堆排序就排好了。

由此可见：建堆和堆删除中都用到了向下调整，掌握向下调整，就可以完成堆排序

实现代码：

typedef int HPDataType;

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

void AdjustDown(HPDataType* a, int n, int parent)//向上调整
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}

		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)//堆排序
{
	// 堆排序思路：选择排序，依次选数，从后往前排
	// 升序 -- 用大堆
	// 降序 -- 用小堆
	// 先建堆 -- 然后向下调整建堆 - O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// 选数
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

int main()
{
	int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 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
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
64
65

2、TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆。
   解释：若求前k个最大的元素，则建小堆；若求前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，替换，向下调整。
   解释：若求前k个最大的元素，建小堆，遍历剩余N-K个元素。若比堆顶元素小，不用动；若比堆顶元素大，就换到堆顶，然后向下调整，就这样直到遍历到最后一个元素，最终堆中剩余的K个元素就是所求的前K个最大的元素。
   反之，若求前k个最小的元素，建大堆，遍历剩余N-K个元素。若比堆顶元素大，不用动；若比堆顶元素小，就换到堆顶，然后向下调整，就这样直到遍历到最后一个元素，最终堆中剩余的K个元素就是所求的前K个最小的元素。

实现代码（借鉴即可）：

typedef int HPDataType;

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}

		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void PrintTopK(int* a, int k, int num)
{
	assert(a);

	// 建k个数的小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(a, k, j);
	}

	// 继续读取后N-K
	int tmp = k;
	while (tmp < num)
	{
		tmp++;
		if (a[tmp] > a[0])//遍历后面的元素，比堆顶大就交换
		{
			a[0] = a[tmp];
			AdjustDown(a, k, 0);
		}

	}

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

int main()
{
	int a[] = { 10,2,5,45,48,7,3,64,82,49,22,0,548,1001,1002,1003,1004 };
	int num = sizeof(a) / sizeof(int);
	PrintTopK(a, 4, num);
	return 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
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
64
65
66
67
68
69

程序应该多加注意细节。
end