五、树(下):7.堆中的路径

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

输入格式:
每组测试第1行包含2个正整数N和M(≤1000)&＃xff0c;分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:
对输入中给出的每个下标i&＃xff0c;在一行中输出从**H[i]**到根结点的路径上的数据。数字间以1个空格分隔&＃xff0c;行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3


输出样例:

24 23 10
46 23 10
26 10

代码

#include
#define MAXN 1001
#define MINH -10000int H[MAXN],size; //H数组是全局变量&＃xff0c;因此才能在Insert函数中修改值 void Create()
{size &＃61; 0;H[0] &＃61; MINH;
}void Insert(int X)
{int i;for(i&＃61;&＃43;&＃43;size;H[i/2]>X;i/&＃61;2)H[i] &＃61; H[i/2];H[i] &＃61; X;
}int main()
{int n,m,x,i,j,s;scanf("%d %d",&n,&m);Create();for(i&＃61;0;i<n;i&＃43;&＃43;){scanf("%d",&x);Insert(x);}for(i&＃61;0;i<m;i&＃43;&＃43;){scanf("%d",&j);s &＃61; 0;while(j>&＃61;1){if(s) printf(" ");s&＃43;&＃43;;printf("%d",H[j]);j/&＃61;2;}printf("\n");}return 0;}

出现的问题和解决方法

最大N和M随机&＃xff0c;元素取到正负10000监测点超时

出现这个问题是因为岗哨H[0]&＃61;MINH里的MINH设大了(设成-1000了)&＃xff0c;导致循环for(i&＃61;&＃43;&＃43;size;H[i/2]>X;i/&＃61;2)不能结束。