05-樹7 堆中的路徑 （25 分)

將一系列給定數字插入一個初始為空的小頂堆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<cstdio>
const int MIN = -10000;
const int maxn = 1010;int H[maxn],size;void insert(int x){int i;for(i = ++size; H[i/2] > x; i /= 2)H[i] = H[i/2];H[i] = x;
}void create(){size = 0;H[0] = MIN;
}int main(){create();int n,m;int v;scanf("%d %d",&n,&m);for(int i = 0; i < n; i++){scanf("%d",&v);insert(v);}for(int i = 0; i < m; i++){scanf("%d",&v);printf("%d",H[v]);while(v > 1){v /= 2;printf(" %d",H[v]);}printf("\n");}return 0;
}

?