将一系列給定數字插入一個初始為空的小頂堆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
###思路：
本題以數組存儲最小堆。依次插入，核心代碼在 resort 函數。每次插入一個元素，放在數組最後，即樹層次周遊的最後一個位置，然後和他的父親節點做比較，如果它大于父親節點的值，則滿足最小堆的定義，否則将它和父親節點做交換，循環直至到根節點或者小于父親節點值。
最小堆：根節點的值比左右節點的值都小的二叉樹，也叫小頂堆/小根堆。
最大堆：根節點的值比左右節點的值都大的二叉樹，也叫大頂堆/大根堆。
#include<stdio.h>
#define N 1002
int h[N]={0};
void resort(int i);
void way2root(int i);
int main(){
int n, m;
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++){//二叉樹從1開始編碼
scanf("%d",h+i);
resort(i);
}
while(m--){
int index;
scanf("%d",&index);
way2root(index);
}
return 0;
}
void resort(int i){
//把新插入的元素,放入到數組最後一個元素
//然後重新組織成最小堆
while(i/2&& h[i/2] > h[i]){
int tmp = h[i];
h[i] = h[i/2];
h[i/2] = tmp;
i /= 2;
}
}
void way2root(int i){
while(i != 1){
printf("%d ",h[i]);
i /= 2;
}
printf("%d\n",h[1]);
}