【建堆(边插入边调整)+路径】输出堆中的路径

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数$N$和$M$(≤)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-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

#include <iostream>
using namespace std;#define MAXN 1001
#define MINH -10001
int H[MAXN], siz;      // 全局变量， 堆的数组和大小
void Create()
{siz = 0;H[0] = MINH;  //设置哨兵
}void Insert(int x)
{if(siz==1000) // 堆已满return;int i;siz++;     // 堆大小加一for (i = siz; H[i/2] > x; i/=2) {H[i] = H[i/2];}H[i] = x;
}int main()
{int N, M, x, j;cin>>N>>M;      Create();       //堆初始化 for(int i=0; i<N; i++) {    //以逐个插入方式建堆 cin>>x;Insert(x);}for(int i=0; i<M; i++) {cin>>j;cout<<H[j];while (j>1) { //沿根方向输出各结点j /= 2;cout<<" "<<H[j];     //输出结点}cout<<endl;}return 0;
}