堆中的路径（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+)*sizeof(int));

  H->size=;

  H->capacity=size;

  H->data[]=-;

  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/]>v;i/=)

  H->data[i]=H->data[i/];

  H->data[i]=v;

}

MinHeap BuildHeap(int n){   //构建堆，先创建堆，再将数据不断加入队中并调整

  MinHeap H=createHeap(n);

  int v;

  for(int i=;i<n;i++){

    scanf("%d",&v);

    insert(H,v);

  }

  return H;

}

void Traverse(MinHeap H,int index){

  int flag=;

  for(;index>;index/=){

    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=;i<m;i++){

      scanf("%d",&index);

      Traverse(H,index);

      printf("\n");

  }

  return ;

}