简答题
偏难
#13201
是不是堆 二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。 时间限制:1000 内存限制:6553…
是不是堆
二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。
时间限制:1000
内存限制:65536
输入
输入在一行中给出两个正整数:m(≤ 100)是将要测试的完全二叉树的数量;n(1 < n ≤ 1000)是完全二叉树中的结点数。 随后 m 行,每行给出 n 个互不相同的键值(均在整型范围内),为完全二叉树的层序遍历序列。
输出
对输入的每棵完全二叉树,如果它是最大堆(大顶堆),就在一行中输出 `Max Heap`;如果是最小堆(小顶堆),则输出 `Min Heap`;如果根本不是堆,则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
3 8 98 72 86 60 65 12 23 50 8 38 25 58 52 82 70 60 10 28 15 12 34 9 8 56
样例输出
Max Heap 50 60 65 72 12 23 86 98 Min Heap 60 58 52 38 82 70 25 8 Not Heap 56 12 34 28 9 8 15 10
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include <iostream>
#include <vector>
using namespace std;
string checkHeap(const vector<int>& tree) {
int n = tree.size();
for (int i = 0; i < n; ++i) {
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && tree[i] > tree[l]) return "Min Heap";
if (r < n && tree[i] > tree[r]) return "Min Heap";
if (l < n && tree[i] < tree[l]) return "Max Heap";
if (r < n && tree[i] < tree[r]) return "Max Heap";
}
return "Not Heap";
}
void printPostOrder(const vector<int>& tree, int i, vector<int>& res) {
if (i >= tree.size()) return;
printPostOrder(tree, 2 * i + 1, res);
printPostOrder(tree, 2 * i + 2, res);
res.push_back(tree[i]);
}
int main() {
int m, n;
cin >> m >> n;
while (m--) {
vector<int> tree(n);
for (int &x : tree) cin >> x;
cout << checkHeap(tree) << endl;
vector<int> res;
printPostOrder(tree, 0, res);
for (int i = 0; i < res.size(); ++i) cout << res[i] << (i == res.size() - 1 ? '\n' : ' ');
}
}</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考代码2
#include <iostream>
#include <vector>
using namespace std;
void postOrder(int index, const vector<int>& arr, vector<int>& res) {
if (index >= arr.size()) return;
postOrder(2 * index + 1, arr, res);
postOrder(2 * index + 2, arr, res);
res.push_back(arr[index]);
}
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> testCases(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> testCases[i][j];
}
}
for (const auto& arr : testCases) {
bool is_max = true, is_min = true;
int size = arr.size();
for (int i = 0; i < size; ++i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size) {
if (arr[i] < arr[left]) is_max = false;
if (arr[i] > arr[left]) is_min = false;
}
if (right < size) {
if (arr[i] < arr[right]) is_max = false;
if (arr[i] > arr[right]) is_min = false;
}
if (!is_max && !is_min) break;
}
if (is_max) cout << "Max Heap\n";
else if (is_min) cout << "Min Heap\n";
else cout << "Not Heap\n";
vector<int> post;
postOrder(0, arr, post);
for (int i = 0; i < post.size(); ++i) {
if (i) cout << ' ';
cout << post[i];
}
cout << endl;
}
return 0;
}</pre><p></p>
这道题暂未补解析。