给定关键码集合，用筛选法构建小顶堆，并按照层序遍历方式输出构建的堆中所有节点。_关键码序列 筛选法建堆

题目：堆的构建 给定关键码集合，用筛选法构建小顶堆，并按照层序遍历方式输出构建的堆中所有节点。

输入样例： 19 8 35 65 40 3 7 45 输出样例： 3 8 7 45 40 35 19 65

示例代码中，我们首先定义了两个函数sift_down()和build_heap()来实现筛选法构建小顶堆的过程，以及一个函数print_tree()来按层序遍历输出所有节点。

sift_down()函数用于将给定的节点下移，以满足小顶堆的定义。该函数的参数包括一个向量nums，表示待构建小顶堆的数组，一个整数root，表示要下移的节点的索引，以及一个整数end，表示下移的最大范围。

在sift_down()函数中，我们首先找到根节点的左子节点，然后将其与右子节点进行比较，并找到两个子节点中较小的一个。然后，如果根节点的值大于其较小的子节点，就将其与较小的子节点交换，并将根节点更新为较小的子节点。然后，我们继续向下移动到较小的子节点，并重复上述过程，直到根节点的值小于或等于其子节点的值，或者已经到达下移的最大范围。

build_heap()函数用于构建小顶堆。该函数的参数为一个向量nums，表示待构建小顶堆的数组。在build_heap()函数中，我们从最后一个非叶节点开始，依次向上调用sift_down()函数，以构建小顶堆。

print_tree()函数用于按层序遍历输出小顶堆中所有节点。该函数的参数为一个向量nums，表示待输出的数组。在print_tree()函数中，我们通过循环遍历数组中的所有元素，并输出它们的值。

最后，在主函数中，我们定义了一个包含给定关键码的向量nums，并依次调用build_heap()函数和print_tree()函数，以构建小顶堆并输出所有节点。

输出结果应该是：

3 8 7 45 40 35 19 65

这就是按照层序遍历方式输出构建的小顶堆中所有节点的结果。

#include <iostream>
#include <vector>

using namespace std;

// 将堆的节点向下移动以满足堆的性质
void sift_down(vector<int>& nums, int root, int end);

// 用输入的数组建立堆
void build_heap(vector<int>& nums);

// 打印堆
void print_tree(vector<int>& nums);

int main() {
	vector<int> nums;
	int num;
	// 输入数组元素
	while (cin >> num) {
		nums.push_back(num);
		// 当遇到回车时停止输入
		if (cin.peek() == '\n') {
			break;
		}
	}
	build_heap(nums);
	print_tree(nums);
	return 0;
}

void print_tree(vector<int>& nums) {
	int n = nums.size();
	// 打印堆的元素
	for (int i = 0; i < n; i++) {
		cout << nums[i] << " ";
	}
	cout << endl;
}

void build_heap(vector<int>& nums) {
	int n = nums.size();
	// 从最后一个非叶子节点开始向下筛选
	for (int i = n / 2 - 1; i >= 0; i--) {
		sift_down(nums, i, n - 1);
	}
}

void sift_down(vector<int>& nums, int root, int end) {
	// 根据当前节点计算左子节点
	int child = root * 2 + 1;
	// 当左子节点存在时继续向下筛选
	while (child <= end) {
		// 比较左右子节点大小，如果右子节点更小则选取右子节点
		if (child + 1 <= end && nums[child] > nums[child + 1]) {
			child += 1;
		}
		// 如果根节点大于子节点，则交换它们，并继续向下筛选
		if (nums[root] > nums[child]) {
			swap(nums[root], nums[child]);
			root = child;
			child = root * 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
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

vector 是 C++ 标准库中的一个动态数组容器，可以在程序运行时根据需要动态地分配内存。与 C 语言中的数组相比，vector
具有更高的灵活性和易用性，可以方便地进行插入、删除、查找等操作，同时也提供了许多方便的函数和算法来操作向量。

使用vector需要包含头文件，可以通过以下方式定义一个 vector 对象：

c++

#include using namespace std;

vector nums; // 定义一个存放 int 类型元素的 vector 对象

其中表示该 vector 对象存储的是 int 类型的元素。

vector 的优点在于它的大小和容量可以在运行时动态地改变，因此可以避免手动管理内存带来的麻烦。同时，vector
支持快速的随机访问和连续的内存分配，这使得它在许多场景下都比较高效。