[数据结构与算法]练习4.3 堆中的路径 (25 分)

堆(Heap)是层次遍历的完全二叉树。父结点比子结点大或小。MaxHeap最大堆（大顶堆）根结点最大，MinHeap最小堆（小顶堆）根结点最小。

浙大版《数据结构（第2版）》题目集

https://pintia.cn/problem-sets/434/problems/6104

练习4.3 堆中的路径 (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

AC代码：

#include<stdio.h>
#include<stdlib.h>
#define MaxData -10001                                  //数组中下标0的哨兵。本程序没用到

typedef int ElemType;
typedef struct HeapStruct * Heap;
struct HeapStruct{
    ElemType * Data;
    int Size, Capacity;
};
Heap Create ( int Maxsize );                            //新建堆
void MinHeapInsert ( Heap H, int x);                    //插入
int IsFull (Heap H);                                    //判断堆是否满
void PrintPath (Heap H, int index);                     //打印路径

int main (){
    int n,m,i,index;
    ElemType x;
    Heap Min = NULL;
    scanf("%d %d",&n,&m);
    Min = Create ( n );
    for(i=0;i<n;i++){
        scanf("%d",&x);
        MinHeapInsert( Min, x); 
    }
    for(i=0;i<m;i++){
        scanf("%d",&index);
        PrintPath( Min, index);
    }
    return 0;
}

Heap Create ( int Maxsize ){                        
    Heap H = (Heap)malloc(sizeof(struct HeapStruct));
    H -> Data = (ElemType*)malloc((Maxsize+1) * sizeof(ElemType)); 
    H -> Size = 0;                        //Data空间是Maxsize+1。堆从下标1开始存放数据。
    H -> Capacity = Maxsize;
    H -> Data[0] = MaxData;
    return H;
}

void MinHeapInsert ( Heap H, ElemType x){
    if(IsFull(H)) return;
    int i = ++ H->Size;                            堆是层次遍历的完全二叉树。
    for(;i>1 && x < H -> Data[i/2]; i/=2){         //用数组来存储，下标/2为父节点下标。
        H -> Data[i] = H -> Data[i/2];  //循环比较，比父结点小，父结点下移，插入位置上移。
    }                               //如果没有下标0哨兵，循环条件必加i>1。1是根结点位置。
    H -> Data[i] = x;
}

int IsFull (Heap H){
    return ( H->Size == H -> Capacity);
}

void PrintPath (Heap H, int index){
    for(; index>0; index/=2){
        printf("%d",H->Data[index]);
        if(index>1) printf(" ");
        else printf("\n");
    }
}