当前位置：首页 > article >正文

完全二叉树的应用--堆

article 2024/12/2 8:59:38

1.堆的概念

2.性质

3.逻辑结构和物理结构（存储结构）

4.堆的实现前提

5.堆的实现

思考：插入数据之前，得保证之前的数据是一个堆。为什么要这样？

思考：为什么先改变 child 的值，先改 parent 的值不可以么？

5.2向下调整建堆

思考：为什么先动parent，后动child？

1.堆的概念

如果有一个关键码的集合K = { 在一个一维数组中，并满足：，， = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.性质

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

3.逻辑结构和物理结构（存储结构）

4.堆的实现前提

4.1思路：

我们用数组用来实现堆。是因为堆是完全二叉树，数据是连续的，没有空数据。既然连续，那么下标之间的关系就可以很好的帮助我们找见父子节点的关系。

注：数组都可以看做是完全二叉树，但是不能都看做堆。因为堆的数据存放前后有大小要求。

4.2下标之间的关系

4.3建什么堆--大堆 / 小堆

5.堆的实现

怎样建堆---向上调整建堆 / 向下调整建堆

5.1向上调整建堆

5.1.1定义：

从根节点开始，找它的父亲，先入堆，再比较父子的大小关系，根据建大/小堆，判断父子是否需要交换，再判断下一个节点。再找它的父亲.......。一直将数据全部入堆之后，就完成向上调整建堆了

注1：从定义看，我们发现，向上调整建堆，就是将数据，从第一个开始，一个接一个入堆，之后再判断是否需要交换。

注2：每当插入一个新节点时，只会影响它绝对路径上的节点（也就是所有祖先节点）。为什么？

因为堆是从无到有的，每当插入一个新节点，插入之前的所有节点就已经是堆了，不需要调整。只需要调整当前新节点。

注3：插入数据之前，得保证之前的数据是一个堆，才可以用向上调整继续建堆。（注2解释了为什么插入之前的数据就已经是堆了）

思考：插入数据之前，得保证之前的数据是一个堆。为什么要这样？

维持堆的性质：如果插入数据之前的结构不是堆，那么在进行向上调整时，可能会导致错误的结果，因为向上调整算法依赖于堆的性质（即每个节点的值都大于或等于其子女节点的值，或者每个节点的值都小于或等于其子女节点的值）

5.1.2代码：

void Swap(HPDataType* a, HPDataType* b) {
	HPDataType* tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustUp(HPDataType* a, HPDataType 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 main() {
	int a[6] = { 32,70,65,60,50,100 };
	for (int i = 0; i < 6; i++) {
		AdjustUp(a, i);
	}
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

5.1.3代码解析：

我们最后一个节点，一直向上调整，如果没有父亲，那么就结束最后一次调整。例如下面这张图

想清楚，child和parent谁先到达根节点？child先到。那么此时child=0,parent=（0-1）/ 2 =0，while循环条件满足，就会造成死循环。

思考：为什么先改变 child 的值，先改 parent 的值不可以么？

也可以这样，那parent改之前的值得先存起来，parent改之后，将存起来的值赋值给child。或者是求改之后的parent的child的child。

综上所诉，先改child，再改parent。

5.2向下调整建堆

5.2.1定义：

跟向上调整一样，向下调整就是找孩子。

有三点区别：1.找哪一个孩子，左孩子还是右孩子？

2.从哪开始向上调整建堆是从根开始，向下调整可以从根开始么？不可以，因为根节点的左右子树不是堆。

3.顺序是从后往前。

注：向上调整建堆可以从根开始，本质是因为它是从根节点开始找父亲节点，然后父子之间判断是否需要交换。然后再找下一个节点。建堆的过程是从无到有的。但是向下调整是找孩子，又需要保证孩子的左右子树都是堆，这次调整才有意义。

注：左右子树都是堆，才可以用向下调整。（参考：向上调整的注3）。

5.2.2代码：

void Swap(HPDataType* a, HPDataType* b) {
	HPDataType* tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustDown(HPDataType* a, int parent, int num) {
	int child = parent * 2 + 1;	

	while (child <= num - 1) {
		if (child + 1 < num) {
			//右孩子存在
			//用假设法，找见较大的那个孩子的下标
			if (a[child + 1] > a[child]) {
				child = child + 1;
			}
		}
		//走到这一步，l_child就是较大值孩子的下标
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent=child;
			child = child * 2 + 1;
		}
		else {
			break;
		}
	}	
}
int main() {
	int a[6] = { 32,70,65,60,50,100 };
	int num = sizeof(a) / sizeof(a[0]);
	for (int i =(num-1-1)/2 ; i >=0; i--) {
		AdjustDown(a, i, num);
	}
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}