PAT 05-树6 Path in a Heap

这次的作业完全是依葫芦画瓢，参照云课堂《数据结构》（http://mooc.study.163.com/learn/ZJU-1000033001#/learn/content）中何钦铭老师课件中有关建堆及插入的内容，再加上自己写的一个矬函数（竟然传了4个参数），OK了！题设要求及代码实现如下

  1 /*
  2     Name: 
  3     Copyright: 
  4     Author: 
  5     Date: 05/04/15 19:34
  6     Description: 
  7 Insert a sequence of given numbers into an initially empty min-heap H. Then for any given index i, you are supposed to print the path from H[i] to the root.
  8 
  9 Input Specification:
 10 
 11 Each input file contains one test case. For each case, the first line gives two positive integers N and M (<=1000) which are the size of the input sequence, and the number of indices to be checked, respectively. Given in the next line are the N integers in [-10000, 10000] which are supposed to be inserted into an initially empty min-heap. Finally in the last line, M indices are given.
 12 
 13 Output Specification:
 14 
 15 For each index i in the input, print in one line the numbers visited along the path from H[i] to the root of the heap. The numbers are separated by a space, and there must be no extra space at the end of the line.
 16 
 17 Sample Input:
 18 5 3
 19 46 23 26 24 10
 20 5 4 3
 21 Sample Output:
 22 24 23 10
 23 46 23 10
 24 26 10
 25 */
 26 
 27 #include <stdio.h>
 28 #include <stdlib.h>
 29 
 30 #define MinData -10001
 31 
 32 typedef struct HeapStruct
 33 {
 34     int * Elements;
 35     int Size;
 36     int Capacity;
 37 } * MinHeap;
 38 
 39 MinHeap Create(int MaxSize);
 40 void Insert(MinHeap H, int item);
 41 void Print(MinHeap H, int * a, int N, int M);
 42 
 43 int main()
 44 {
 45 //    freopen("in.txt", "r", stdin); // for test
 46     int N, M, i, item;
 47     MinHeap H;
 48     
 49     scanf("%d%d", &N, &M);
 50     
 51     H = Create(N);
 52     for(i = 0; i < N; i++)
 53     {
 54         scanf("%d", &item);
 55         Insert(H, item);
 56     }
 57     
 58     int a[M];
 59     
 60     for(i = 0; i < M; i++)
 61         scanf("%d", &a[i]);
 62         
 63     Print(H, a, N, M);
 64 //    fclose(stdin); // for test
 65     return 0;
 66 }
 67 
 68 MinHeap Create(int MaxSize)
 69 {
 70     MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
 71     H->Elements = (int *)malloc((MaxSize + 1) * sizeof(int));
 72     H->Size = 0;
 73     H->Capacity = MaxSize;
 74     H->Elements[0] = MinData;
 75     
 76     return H;
 77 }
 78 
 79 void Insert(MinHeap H, int item)
 80 {
 81     int i;
 82     
 83     i = ++H->Size;
 84     for(; H->Elements[i / 2] > item; i /= 2)
 85         H->Elements[i] = H->Elements[i / 2];
 86     H->Elements[i] = item;
 87 }
 88 
 89 void Print(MinHeap H, int * a, int N, int M)
 90 {
 91     int i;
 92     
 93     for(i = 0; i < M; i++)
 94     {
 95         if(a[i] <= N)
 96         {
 97             while(a[i])
 98             {
 99                 printf("%d", H->Elements[a[i]]);
100                 if(a[i] > 1)
101                     printf(" ");
102                 else
103                     printf("
");
104                 a[i] /= 2;
105             }
106         }
107     }
108 }