7-5 堆中的路径 (25 分)
将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数$N$和$M(\leq 1000)$，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的$N$个要被插入一个初始为空的小顶堆的整数。最后一行给出$M$个下标。
输出格式:
对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
输入样例:
1
2
3
| 5 3
46 23 26 24 10
5 4 3
|
输出样例:
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
| #include<stdio.h>
#include<stdlib.h>
#define max 1005
#define min -10001
void Create();
void Insert( int temp);
int h[max],size;
int main()
{
int n,m;
int temp;
int i,j;
scanf("%d %d",&n,&m);
Create();
for( i=0; i<n; i++){
scanf("%d",&temp);
Insert(temp);
}
for( i=0; i<m; i++){
scanf("%d",&j);
printf("%d",h[j]);
while( j>1 ){
j /= 2;
printf(" %d",h[j]);
}
printf("\n");
}
return 0;
}
void Create()
{
size = 0;
h[0] = min;
}
void Insert( int temp)
{
int i;
for( i=++size; h[i/2]>temp;i/=2){
h[i] = h[i/2];
}
h[i] =temp;
}
|
