小白专场:堆中的路径

2020-03-16 71浏览

  • 1.小白专场:堆中的路径
  • 2.题意理解 将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给 定的下标`i`,打印从H[i]到根结点的路径。 ### 输入样例: 53 46 23 26 24 10 543 ### 输出样例: 24 23 10 46 23 10 26 10 [1] 10 [2] 23 [3] 26 46 24 [4] [5]
  • 3.堆的表示及其操作 #define MAXN 1001 #define MINH -10001 void Insert ( int X ) { /* 将X插入H。这里省略检查堆是否已满的代码 */ int H[MAXN], size; int i; void Create () { size = 0; H[0] = MINH; /*设置“岗哨”*/ } for (i=++size; H[i/2] > X; i/=2) H[i] = H[i/2]; H[i] = X; }
  • 4.主程序 int main() { 读入n和m 根据输入序列建堆 对m个要求:打印到 根的路径 int main() { int n, m, x, i, j; scanf("%d %d", &n, &m); Create(); /* 堆初始化 */ for (i=0; i1) { /*沿根方向输出各结点*/ j /= 2; printf(" %d", H[j]); } printf("\n"); } return 0; }