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

1 题目原文

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

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

输入格式:

每组测试第 $1$ 行包含 $2$ 个正整数 $n$ 和 $m(\le 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;
}

注意题目的下标是从 $1$ 开始的，代码中的堆的下标是从 $0$ 开始的。