2.5 堆中的路径（树，c）

堆中的路径

• • • 题意理解
    • 堆表示及操作
    • 主程序
    • 源代码
    • • 运行

05-树7 堆中的路径

题意理解

• 输入样例:

5 346 23 26 24 105 4 3

• 输出样例:

24 23 1046 23 1026 10

5代表插入的数据是5个，3即3次查询
46 23 26 24 10即要插入的数据
5 4 3即要查询的数据的下标
比如5，对应值为24，就要求打印出24 23 10这条路径

堆表示及操作

最小堆，父节点比儿子结点的值小，从最后一个元素的下一个元素开始，即++size，每次和父节点比较，如果父节点大就挪下来，H[i] = H[i/2];把i挪到父节点的位置i/=2;当父节点小于等于它的时候就退出来，再把X放进去H[i]=x;

主程序

0到m-1的循环，每次循环里面读进一个数，把这个数赋值给 j ，代表当前查询的位置，把这个位置的元素值打印出来，
接下来要打印 j 的父亲，把 j 这个位置到根节点路径上的所有祖先都打印出来，当 j >1是代表还没到根的时候，因为根的位置是1，所以大于1就是代表还没到根，就把 j/2 ，代表父节点的位置了，把父节点值打印出来，再循环看看 j 大不大于1，如果还不大于，那么再j/2，再打印，最后打印出回车

源代码

#include#include#define MAXN 1001#define MINH -10001int H[MAXN], size;void Create();void Insert(int X);int main() {int n, m, x, i, j;scanf("%d %d", &n, &m);Create();  /*堆初始化*/for (i = 0; i < n; i++) { /*以逐个方式插入建堆*/scanf("%d", &x);Insert(x);}for (i = 0; i < m; i++) {scanf("%d", &j);printf("%d", H[j]);while (j > 1) {/*沿根方向输出各结点*/j /= 2;printf(" %d", H[j]);}printf("\n");}return 0;}void Create() {size = 0;H[0] = MINH;/*设置“岗哨”*/}void Insert(int X) {/*将X插入H,检查堆是否已满*/int i;if (size >= MAXN){printf("最小堆已满！");return;}for (i = ++size; H[i / 2] > X; i /= 2) {H[i] = H[i / 2];}H[i] = X;}

运行

5 346 23 26 24 105 4 324 23 1046 23 1026 10