【编程题】7-5 堆中的路径

7-5 堆中的路径

1 题目原文
2 思路解析
3 代码实现

1 题目原文

题目链接：7-5 堆中的路径

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

输入格式:

每组测试第 $1$ 行包含 $2$ 个正整数 $n$ 和 $m (≤10^3)$ ，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间 $10^4,10^4 ]$ 内的 $n$ 个要被插入一个初始为空的小顶堆的整数。最后一行给出 $m$ 个下标。

输出格式:

对输入中给出的每个下标 $i$ ，在一行中输出从第 $i$ 个结点到根结点的路径上的数据。数字间以 $1$ 个空格分隔，行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

2 思路解析

此题考查最小堆。
1. 定义最小优先队列 pq；
2. 按照题目要求，遍历所给数组，依次将元素加入 pq，操作完之后即获得了一个最小堆；
3. 根据所给下标，从下往上依次遍历输出堆中的元素，直到根结点，即堆中的路径，注意题目中的下标和自定义的堆中的下标。
堆和优先队列可以参考这篇文章，这里不再赘述其原理和实现过程，只给出代码实现（应用）。

3 代码实现

#include <stdio.h>
#include <stdlib.h>

int* create_heap(int n) {
    int* res = (int*)malloc(n * sizeof(int));
    return res;
}

/** 此题中只需要入队，所以只实现上浮操作即可 **/
void adjust_up_heap(int* heap, int n) {
    int t = heap[n], i = (n - 1) >> 1;
    while (i >= 0 && t < heap[i]) {
        heap[n] = heap[i];
        n = i;
        i = (i - 1) >> 1;
    }
    heap[n] = t;
}

int* find_path_to_root(int* heap, int i, int* n) {
    int* res = (int*)malloc(*n * sizeof(int));
    int j = i, p = 0;
    while (j >= 0) {
        res[p++] = heap[j];
        j = (j - 1) >> 1;
    }
    res = (int*)realloc(res, p * sizeof(int));
    *n = p;
    return res;
}

void destroy_arr(int* arr) { free(arr); }

int main(void) {
    int n = 0, m = 0, i = 0, j = 0, k = 0;
    scanf("%d%d", &n, &m);
    int* heap = create_heap(n);
    for (i = 0; i < n; i++) {
        scanf("%d", heap + i);
        adjust_up_heap(heap, i);
    }
    while (m--) {
        scanf("%d", &i);
        k = n;
        int* r = find_path_to_root(heap, i - 1, &k);
        printf("%d", r[0]);
        for (j = 1; j < k; j++) {
            printf(" %d", r[j]);
        }
        printf("\n");
        destroy_arr(r);
    }
    destroy_arr(heap);
    return 0;
}