编程题7-5-堆中的路径
目录
【编程题】7-5 堆中的路径
1 题目原文
题目链接：
将一系列给定数字插入一个初始为空的最小堆
h h
h 。随后对任意给定的下标
i i
i ，打印从第
i i
i 个结点到根结点的路径。
输入格式:
每组测试第
1 1
1 行包含
2 2
2 个正整数
n n
n 和
m ( ≤ 1 0 3 ) m (≤10^3)
m
(
≤
1
0
3
) ，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间
[ − 1 0 4 , 1 0 4 ] [−10^4,10^4 ]
[
−
1
0
4
,
1
0
4
] 内的
n n
n 个要被插入一个初始为空的小顶堆的整数。最后一行给出
m m
m 个下标。
输出格式:
对输入中给出的每个下标
i i
i ，在一行中输出从第
i i
i 个结点到根结点的路径上的数据。数字间以
1 1
1 个空格分隔，行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3输出样例:
24 23 10
46 23 10
26 102 思路解析
此题考查最小堆。
定义最小优先队列
pq；按照题目要求，遍历所给数组，依次将元素加入
pq，操作完之后即获得了一个最小堆；根据所给下标，从下往上依次遍历输出堆中的元素，直到根结点，即堆中的路径，注意题目中的下标和自定义的堆中的下标。
堆和优先队列可以参考 ，这里不再赘述其原理和实现过程，只给出代码实现（应用）。
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 1
1 开始的，代码中的堆的下标是从
0 0
0 开始的。