05-树7 堆中的路径 (25 分)【每日一题】

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-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

Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MinData -10001

typedef struct Heap *MinHeap;
typedef int ElementType;
struct Heap{
    ElementType *Elements;
    int Size;    //记录当前堆元素个数
    int Capacity;   //堆的最大容量
};

void Insert(MinHeap H,ElementType X);
MinHeap Create(int MaxSize);
void PrintRoad(MinHeap H,int k);

int main()
{
    /*算法： 1.创建空堆 2.根据输入数据一个个插入元素 3.根据给定的当前元素遍历其父节点并输出 */
    int N,M,X,K;
    scanf("%d %d",&N,&M);
    MinHeap H = Create(N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&X);
        Insert(H,X);
    }

    for(int i=0;i<M;i++)
    {
        scanf("%d",&K);
        PrintRoad(H,K);
    }
    return 0;
}

MinHeap Create(int MaxSize)
{
    MinHeap H = (MinHeap)malloc(sizeof(struct Heap));
    H->Elements = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    //定义下标为0的位置为“哨兵”，其数值小于小頂堆的最小值
    H->Elements[0] = MinData;
    return H;
}

void Insert(MinHeap H,ElementType X)
{
    int i;
    i = ++H->Size;
    H->Elements[i] = X;
    /*remark:由于我们定义了哨兵H->Elements[0]， 循环到下标为零时，必会结束循环*/
    while(X<H->Elements[i/2])
    {
        H->Elements[i] = H->Elements[i/2];
        H->Elements[i/2] = X;
        i/=2;
    }
}

void PrintRoad(MinHeap H,int k)
{
    while(k>1)
    {
        printf("%d ",H->Elements[k]);
        k/=2;
    }
    printf("%d\n",H->Elements[1]);
}