堆中的路径（MOOC）

将一系列给定数字插入一个初始为空的小顶堆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


思路：二叉堆的基本构建过程，打印从H[i]到根结点路径用一个for 循环for(;index>0;index/=2)即可打印输出。
本题主要训练二叉堆的构建，用struct 结构体构建Heap的结构。

#include<stdio.h>
#include<stdlib.h>
typedef struct HNode *Heap;
struct HNode{
  int *data;    
  int size;
  int capacity;
};

typedef Heap MinHeap;   //最小堆

MinHeap createHeap(int size){     //创建一个二叉堆
  MinHeap H=(MinHeap)malloc(sizeof(struct HNode));
  H->data=(int*)malloc((size+1)*sizeof(int));
  H->size=0;
  H->capacity=size;
  H->data[0]=-11111;
  return H;
}
bool isFull(MinHeap H){
  return (H->size==H->capacity);
}
void insert(MinHeap H,int v){   //将输入的V值加入最小堆中，并不断调整
  int i;
  if(isFull(H))return;
  i=++H->size;
  for(;H->data[i/2]>v;i/=2)
  H->data[i]=H->data[i/2];
  H->data[i]=v;
}
MinHeap BuildHeap(int n){   //构建堆，先创建堆，再将数据不断加入队中并调整
  MinHeap H=createHeap(n);
  int v;
  for(int i=0;i<n;i++){
    scanf("%d",&v);
    insert(H,v);
    
  }
  return H;
}
void Traverse(MinHeap H,int index){
  int flag=0;
  for(;index>0;index/=2){
    if(flag++)printf(" ");
    printf("%d",H->data[index]);
  }
}
int main(){
  int n,m;
  Heap H;
  scanf("%d %d",&n,&m);
  H=BuildHeap(n);
  int index;
  for(int i=0;i<m;i++){
      scanf("%d",&index);
      Traverse(H,index);
      printf("
");
  }
  return 0;
}