题意理解
- 输入样例:
5 3
46 23 26 24 10
5 4 3
- 输出样例:
24 23 10
46 23 10
26 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<stdio.h>
#include<stdlib.h>
#define MAXN 1001
#define MINH -10001
int 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 3
46 23 26 24 10
5 4 3
24 23 10
46 23 10
26 10
