PAT (Advanced Level) Practice 1147 Heaps (30 分) 凌宸1642

本文主要是介绍PAT (Advanced Level) Practice 1147 Heaps (30 分) 凌宸1642，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

PAT (Advanced Level) Practice 1147 Heaps (30 分) 凌宸1642

题目描述：

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

Your job is to tell if a given complete binary tree is a heap.

译：在计算机科学中，堆是一种特殊的基于树的数据结构，它满足堆属性：如果 P 是 C 的父节点，则 P 的键（值）要么大于或等于（在最大堆中） ) 或小于或等于（在最小堆中）C 的键。堆的常见实现是二叉堆，其中树是完全二叉树。 （引自维基百科 https://en.wikipedia.org/wiki/Heap_(data_structure)）

你的工作是判断一个给定的完整二叉树是否是一个堆。

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 100), the number of trees to be tested; and N (1 < N ≤ 1,000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行给出两个正整数：M（≤ 100），要测试的树的数量； 和 N (1 < N ≤ 1,000)，分别是每棵树中的键数。 然后是 M 行，每行包含 N 个不同的整数键（都在 int 范围内），这给出了完整二叉树的层序遍历序列。

output Specification (输出说明):

For each given tree, print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all. Then in the next line print the tree's postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

译：对于每个给定的树，如果它是最大堆，则在一行中打印 Max Heap，如果是最小堆，则打印为Min Heap，如果根本不是堆，则打印为 Not Heap。 然后在下一行打印树的后序遍历序列。 所有数字之间用空格隔开，行首或行尾不得有多余空格。

Sample Input (样例输入):

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

Sample Output (样例输出):

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

The Idea：

• 直接建树的话，最后两个测试点会超时。

• 利用堆的性质，可以不见树即可判断是否是堆，然后由于需后序遍历，最后一个结点一定是根节点，所以可以直接对数组使用 dfs 。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
int layer[1010] , m , n ;
void dfs(int root){
	if(root > n ) return ;
	dfs(root * 2) ;
	dfs(root * 2 + 1) ;
	cout << layer[root] << ((root == 1)?'\n':' ') ;
 }
int main(){
	cin >> m >> n ;
	for(int i = 0 ; i < m ; i ++){
		for(int j = 1 ; j <= n ; j ++) cin >> layer[j] ;
		bool minHeap = true , maxHeap = true ;
		for(int j = 1 ; j <= n ; j ++){
			if(j > 1 && layer[j/2] > layer[j]) minHeap = false ;
			if(j > 1 && layer[j/2] < layer[j]) maxHeap = false ;
		}
		if(maxHeap) cout << "Max Heap" << endl ;
		else if(minHeap) cout << "Min Heap" << endl ;
		else cout << "Not Heap" << endl ;
		dfs(1) ;
	}
	return 0 ;
}

这篇关于PAT (Advanced Level) Practice 1147 Heaps (30 分) 凌宸1642的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！