【数据结构】二叉树的顺序结构及实现，堆，向上调整算法，向下调整算法，数组建堆算法，堆排序

提示：学习本文之前，要先了解一下树的概念及结构，二叉树的概念及结构，详情请至博客。

---

1.二叉树的顺序结构

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

2.堆的概念及结构

如果有一个关键码的集合K={k0,k1,k2,…,Kn-1},把它的所有元素按完全二叉树的顺序表存储方式存储在一个一维数组中，并满足以下情况：

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

3.堆的实现

3.1堆的总实现

堆的实现代码（全），请点击——>堆的实现代码

3.2堆的向上调整算法—O(logN)

使用场景：向堆中插入数据，需要使用向上调整算法，因为向堆中插入数据是将数据插入到下标为size的位置，插入一个数据，size++，此时可能就不满足小堆（或大堆），因此要对其进行调整，此处以小堆为例，向上调整算法只需要从插入的结点位置开始和父节点比较（一路和祖先进行比较），若a[child]=a[parent],则满足小堆，直接break，跳出循环。同时，循环结束的条件是child==0,因为此时小数已经到达堆顶，调整完成。—一遍建堆，一遍调整

代码实现：（以建小堆为例）

void Swap(HPDataType* e1, HPDataType* e2)
{
	HPDataType tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
void AdjustUp(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;
		}
	}
}
//插入x，继续保持堆形态
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
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

3.3堆的向下调整算法—O(logN)

1.使用场景：删除堆顶元素HeapPop，需要用到堆的向下调整算法。
删除堆顶元素，作用：找次大的数或者次小的数—时间复杂度O(logN)
方法：在删除堆顶元素时用到了向下调整算法，建立了一个小堆，如果我们使用向前挪动数组元素的方法，删除堆顶元素，时间复杂度为O(N);如果先将堆顶元素和最后一个元素交换，然后size–，删除这个元素，再用向下调整算法，时间复杂度就是O(logN)。
2.向下调整算法的前提是：当前的树左右子树必须都是一个堆
3.算法的核心思想：从根结点开始，选出左右孩子中小的那一个，跟父亲交换，因为是建小堆（原来的堆是小堆），所以小的往上交换，大的往下沉，如果要建大堆则相反。

下图是在利用向下调整算法建一个小堆：

代码实现：（建小堆为例）

//向下调整算法---O(logN)
void AdjustDown(HPDataType* a,int size,int parent)
{
	//先假设左边的孩子是最小的
	int minchild = parent * 2 + 1;
	while (minchild < size)
	{
		//找出小的那个孩子进行交换
		if (minchild+1<size && a[minchild + 1] < a[minchild])
		{
			minchild += 1;
		}
		if (a[minchild] < a[parent])
		{
			Swap(&a[parent], &a[minchild]);
			parent = minchild;
			minchild = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)//删除堆中的数据。保持堆形态
{
	assert(php);
	assert(!HeapEmpty(php));
	//方法：交换堆顶和最后一个元素
	//如果用挪动的方式，时间复杂度为O(N),而用向下调整算法，时间复杂度只有O(logN)
	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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4.数组建堆算法（建大堆）

下面我们给出一个数组，这个数组逻辑上可以看做一棵完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。那么根结点的左右子树不是堆，我们怎么调整呢？这里介绍两种算法，优先使用向下调整算法，时间复杂度更优。

数组建堆代码的实现，请点击——>数组建堆算法

4.1向上调整建堆

在原数组的基础上（物理上），第一个元素保持不动，之后的元素类似HeapPush,堆的插入，向上调整建堆。向上调整建堆的时间复杂度分析：O(N*logN)

代码实现：

#include
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
void AdjustUp(int* 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;
		}
	}
}
//向上调整算法建堆
void HeapCreate(int* a, int n)
{
	//向上调整建堆,第一个元素保持不动
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);//物理上是个数组，在数组的基础上建堆,从第2个数据开始插入，一边插入一边建堆
	}
}
void HeapPrint(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	int a[] = { 65,100,60,32,50,70 };
	//int a[] = { 15,1,19,25,8,34,65,4,27,7 };

	HeapCreate(a, sizeof(a) / sizeof(a[0]));
	HeapPrint(a, sizeof(a) / sizeof(a[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

4.2向下调整建堆

向下调整建堆，从倒数第一个非叶子结点（最后一个结点的父亲）开始向下调整，调整完后，下标–，到另一个子树调整，直到调整到根。时间复杂度分析：O(N),优于向上调整建堆，分析见下图：

代码实现：

void AdjustDown(int* a, int size, int parent)
{
	//先假设左边的孩子是最小的
	int minchild = parent * 2 + 1;
	while (minchild < size)
	{
		//找出小的那个孩子
		if (minchild + 1 < size && a[minchild + 1] > a[minchild])
		{
			minchild ++;
		}
		if (a[minchild] > a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapCreate(int* a, int n)
{
	//向上调整建堆,第一个元素保持不动
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);//物理上是个数组，在数组的基础上建堆,从第2个数据开始插入，一边插入一边建堆
	//}
	//向下调整建堆
	//n-1是最后一个数据的下标，再-1/2算的就是最后一个结点的父节点
	for (int i=(n - 1 - 1)/2;i>=0; i--)
	{
		AdjustDown(a, n, 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
25
26
27
28
29
30
31
32
33
34
35
36
37

5.堆排序

堆排序实现代码，请点击——>堆排序代码

1.堆排序的大思路，也是一种选择排序。大多数学生认为如果是排升序，建的是小堆，排降序建的是大堆，其实结果是相反的。
升序—建大堆
降序—建小堆
2.推论：假设我们排升序，建的是小堆，思路是，先用向下调整算法建一个小堆，时间复杂度为O(N),堆顶就是第一次找出的最小数，然后再将剩下的数据看成堆，重新建堆，选次小的数据。这种算法可以是可以，但是太多此一举了，并且整体下来的时间复杂度为O(N^2)。
假设升序—建大堆，思路是，先把一开始建好的大堆，第一个数据和最后位置交换，这样就排好了最大的那个数据，然后不把最后一个数据看作堆里面的，继续向下调整建堆，选出次大的，与倒数第二个数据交换，后续一次处理。这样整体下来的时间复杂度就是O(N*logN)

void HeapSort(int* a, int n)
{
	//堆排序的大思路，也是一种选择排序
	//升序---大堆
	//降序---小堆
	//先建堆：向下调整建堆---O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//此时堆顶是最大元素，交换堆顶元素与最后一个元素
	//再将剩下的n-1个元素重新向下调整，找到次大的
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n-i, 0);
		i++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21