将一系列给定数字依次插入一个初始为空的小顶堆H[]
。随后对任意给定的下标i
,打印从H[i]
到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i
,在一行中输出从H[i]
到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3
输出样例:
24 23 10
46 23 10
26 10
这一题我犯了一个巨新手的错误,在up维护最小堆的函数中,没有使用引用,导致我花了很长时间取找它为什么不正确,以后一定要记住这个点
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// 堆化操作,使得从节点i开始向上调整,维护最小堆性质
void up(vector<int>& st, int i) {
while (i > 0 && st[(i - 1) / 2] > st[i]) { // 如果当前节点的值比父节点的值小,交换它们
swap(st[i], st[(i - 1) / 2]);
i = (i - 1) / 2; // 更新当前节点的索引为其父节点的索引
}
}
// 打印从节点i到根节点的路径
void findpath(vector<int> st, int i) {
while (i > 0) {
cout << st[i] << " "; // 打印当前节点的值
i = (i - 1) / 2; // 更新当前节点的索引为其父节点的索引
}
cout << st[0]; // 打印根节点的值
cout << endl; // 换行
}
int main() {
int n, m;
cin >> n >> m; // 输入堆的大小n和查询的数量m
vector<int> heap;
for (int i = 0; i < n; i++) {
int num;
cin >> num; // 依次输入堆中的元素
heap.push_back(num); // 将元素添加到堆中
up(heap, i); // 调整堆,使其满足最小堆性质
}
for (int i = 0; i < m; i++) {
int index;
cin >> index; // 输入查询的节点索引
findpath(heap, index - 1); // 打印从查询节点到根节点的路径
}
return 0;
}