本文主要是介绍数据结构与算法题目集|7-5 堆中的路径 c++满分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
将一系列给定数字依次插入一个初始为空的小顶堆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和查询的数量mvector<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;
}
这篇关于数据结构与算法题目集|7-5 堆中的路径 c++满分题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
