05-树7 堆中的路径 (25分)

2023-12-09 12:08

文章标签 路径 25 05 堆中

本文主要是介绍05-树7 堆中的路径 (25分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

05-树7 堆中的路径 (25分)

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

输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:

对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

插入调整有两种，一种用Insert()调整，一种用HeapCreate()调整，效率肯定是Insert()高，但是HeapCreate()也要掌握

#include<bits/stdc++.h>
using namespace std;int Data[20005] = {0}, Size = 0;void CreateHeap();
void Perc(int root);
void Print(int child);
void Insert();int main() {int N, k, child;cin >> N >> k;Data[0] = -20000;for (int i = 1; i <= N; i++) {cin >> Data[i];Size++;Insert();
//		CreateHeap();}while (k--) {cin >> child;Print(child);cout << endl;}return 0;
} void CreateHeap() {int i = Size / 2;for (; i > 0; i--) {Perc(i);}
}void Perc(int root) {int X = Data[root], Parent = root, Child;for (; Parent * 2 <= Size; Parent = Child) {Child = Parent * 2;if (Child != Size && Data[Child] > Data[Child + 1])Child++;if (X <= Data[Child]) break;else Data[Parent] = Data[Child];}Data[Parent] = X;
}
void Insert() {int i = Size, X = Data[Size];for (; X < Data[i / 2]; i /= 2)Data[i] = Data[i / 2];Data[i] = X;
}
void Print(int child) {int flag = 0;while (child > 0) {if (!flag) {printf("%d", Data[child]);flag = 1;}else printf(" %d", Data[child]);child /= 2;}
}