PAT 05-ツリー6 Path in a Heap
13220 ワード
今回の作業は全くなぞらえで、雲教室の「データ構造」を参照してください.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 }