PTA数据结构与算法题目集(中文) 7-5

PTA数据结构与算法题目集(中文) 7-5 堆中的路径

7-5 堆中的路径 (25 分)

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

题目分析:考查最小堆(优先队列)的实现 需要注意的是 利用插入操作建立最小(大)堆 和  先把数据读入完全二叉树 再调整的方法 可能建成的堆不同 并且他们的时间复杂度也不同(插入操作所需要的时间复杂度为 o(nlogn) 第二种方法的时间复杂度为 线性时间)

 #define _CRT_SECURE_NO_WARNINGS

 #include<stdio.h>

 #include<stdlib.h>

 #include<malloc.h>

 typedef struct HeapStruct* MinHeap;

 struct HeapStruct

 {

     int Size;

     int Capacity;

     int* Elements;

 };

 MinHeap CreatMinHeap(int Capacity)

 {

     MinHeap H;

     H = (MinHeap)malloc(sizeof(struct HeapStruct));

     H->Capacity = Capacity;

     H->Elements = (int*)malloc(H->Capacity * sizeof(int));

     H->Size = -;

     return H;

 }

 void Insert(MinHeap H, int Element)

 {

     int i = ++H->Size;

     for (; i >  && Element < H->Elements[(i - ) / ]; i = (i - ) / )

         H->Elements[i] = H->Elements[(i - ) / ];

     H->Elements[i] = Element;

 }

 void Delete(MinHeap H)

 {

     int Tmp = H->Elements[H->Size--];

     int Parent;

     int Child;

     for (Parent=;(Parent*+)<=H->Size;Parent=Child)

     {

         Child = Parent *  + ;

         if (Child != H->Size && H->Elements[Child] > H->Elements[Child + ])

             Child++;

         if (Tmp <= H->Elements[Child])break;

         else

             H->Elements[Parent] = H->Elements[Child];

     }

     H->Elements[Parent] = Tmp;

 }

 void PrecDown(MinHeap H,int i)

 {

     int Tmp = H->Elements[i];

     int  Parent;

     int Child;

     for (Parent = i; (Parent *  + ) < H->Size; Parent = Child)

     {

         Child = Parent *  + ;

         if (Child != H->Size && H->Elements[Child] > H->Elements[Child + ])

             Child++;

         if (Tmp <= H->Elements[Child])break;

         else

             H->Elements[Parent] = H->Elements[Child];

     }

     H->Elements[Parent] = Tmp;

 }

 void BuildHeap(MinHeap H)

 {

     for (int i = (H->Size - ) / ; i>=; i--)

         PrecDown(H, i);

 }

 void Print(MinHeap H,int i)

 {

     while (i>)

     {

         printf("%d ", H->Elements[i]);

         i = (i - ) / ;

     }

     printf("%d", H->Elements[]);

 }

 int main()

 {

     int N, M;

     scanf("%d %d", &N, &M);

     MinHeap H = CreatMinHeap(N);

     for (int i = ; i < N; i++)

     {

         int num;

         scanf("%d", &num);

         Insert(H, num);

     }

     for (int j = ; j < M; j++)

     {

         int i;

         scanf("%d", &i);

         Print(H, i-);

         printf("\n");

     }

 }

巴特西