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

【数据结构】_堆的向上调整和向下调整建堆法

article 2025/2/13 1:52:00

1. 向上调整建堆法

1.1 思路及时间复杂度

1.2 实现及测试

2. 向下调整建堆法

2.1 思路及时间复杂度

2.2 实现及测试

1. 向上调整建堆法

1.1 思路及时间复杂度

1、调整思路：

建堆时，每创建一个新结点就将其插入到最末的叶结点位置，然后调用向上调整方法使其满足大根堆或小根堆特性；

2、时间复杂度：

1.2 实现及测试

for (int i = 1; i < n; i++) {
		AdjustUp(a, i);
	}

对使用向上调整建堆法进行测试：

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
// 向上调整建堆法
void TestCreateHeapUp() {
	int a[] = { 4,2,8,1,5,6,9,7 };
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = 1; i < n; i++) {
		AdjustUp(a, i);
	}
	printf("CreateHeapUp: maxHeap array: \n");
	for (size_t i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

int main() {
	TestCreateHeapUp();
	return 0;
}

运行结果如下：

2. 向下调整建堆法

2.1 思路及时间复杂度

1、调整思路：

从倒数的第一个非叶子结点（最末子结点的父结点）开始调用向下调整方法。使以该结点为根结点的子树满足小根堆或大根堆特性。

2、时间复杂度

2.2 实现及测试

for循环条件：最末叶结点下标为n-1，其父结点的下标为(n-1-1)/2，即(n-2)/2，直至调整到下标为0的堆顶结点位置：

	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}

对其进行测试：

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
// 向下调整建堆法
void TestCreateHeapDown() {
	int a[] = { 4,2,8,1,5,6,9,7 };
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	printf("CreateHeapDown: maxHeap array: \n");
	for (size_t i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main() {
	TestCreateHeapDown();
	return 0;
}

运行结果如下：