题目

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

思路

简单中的简单题

  1. 输入N、M，初始化空堆
  2. 读入堆元素插入并依次排序
  3. 读入下标输出对应元素
  4. 将下标/2继续输出元素，直到堆顶

源码实现

直接使用堆函数模板代入，代码略微复杂的版本

#include <stdio.h>

typedef struct HeapNode *Heap;
struct HeapNode{
    int *data;
    int size;
};

Heap create(int N);
int insert(Heap H,int X);

int main()
{
    int N,M,X,j;
    Heap H;
    scanf("%d %d",&N,&M);
    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",&j);
        while(j>1){
            printf("%d ",H->data[j]);
            j=j/2;
        }
        printf("%d\n",H->data[j]);
    }
    return 0;
}

Heap create(int N)
{
    Heap H = (Heap)malloc(sizeof(struct HeapNode));
    H->data=(int *)malloc((N+1)*sizeof(int));
    H->size=0;
    H->data[0]=-10001;
    return H;
}

int insert(Heap H,int X)
{  
    int i;
    i=++H->size;
    for(;H->data[i/2]>X;i=i/2){
        H->data[i]=H->data[i/2];
    }
    H->data[i]=X;
    return 1;
}

不使用结构，直接使用数组的版本

#include <stdio.h>

int H[1001];
int size;

void create();
void insert(int X);

int main()
{
    int N=0,M,X,j;
    scanf("%d %d",&N,&M);
    create();
    for(int i=0;i<N;i++){
        scanf("%d",&X);
        insert(X);
    }
    for(int i=0;i<M;i++){
        scanf("%d",&j);
        while(j>1){
            printf("%d ",H[j]);
            j=j/2;
        }
        printf("%d\n",H[j]);
    }
    return 0;
}

void create()
{
    H[0]=-10001;
    size=0;
}

void insert(int X)
{  
    int i;
    i=++size;
    for(;H[i/2]>X;i=i/2){
        H[i]=H[i/2];
    }
    H[i]=X;
}

难点

没有，唯一需要注意的点是本题是边插入边排序如果先插入完后排序会导致5和3的元素互换