A1147 Heaps (30 point(s))

大小根堆判断+后序遍历

1. 原文

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.

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.

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.

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

2. 解析

堆判断：

大根堆 ：根>左结点 && 根>左结点 ；level[0]>level[1] 预测为大根堆 flag=1

小根堆 ：根<左结点 && 根<左结点 ；level[0]<level[1] 预测为小根堆 flag=-1

再根据flag判断：

• flag=1 判断 level[i]<level[2i+1] || level[i]<level[2i+2] 存在则不是大根堆
• flag=-1 判断 level[i]>level[2i+1] || level[i]>level[2i+2] 存在则不是小根堆

后序遍历：

左右根

postorder(2i+1)

postorder(2i+2)

printf(“%d”,level[i]);

3. AC代码

#include<cstdio>
int level[1010]={};
int n;
int key=0;
void postorder(int root)
{
	if (root>=n)
	{
		return;
	}
	postorder(2*root+1);
	postorder(2*root+2);
	if (key!=0)
	{
		printf(" ");
	}else{
		key++;
	}
	printf("%d",level[root]);
}
int main()
{
	int m;
	scanf("%d%d",&m,&n);
	while(m--)
	{
		for (int i = 0; i < n; ++i)
		{
			scanf("%d",&level[i]);
		}
		int flag=-1;
		if (level[0]>level[1])
		{
			flag=1;
		}
		for (int i = 0; i <= (n-1)/2; ++i)
		{
			int left=2*i+1;
			int right=2*i+2;
			if (flag==1)
			{
				if ((level[i]<level[left]&&left<n)||(level[i]<level[right]&&right<n))
				{
					flag=0;
				}
			}
			if (flag==-1)
			{
				if ((level[i]>level[left]&&left<n)||(level[i]>level[right]&&right<n))
				{
					flag=0;
				}
			}
		}
		if (flag==0)
		{
			printf("Not Heap\n");
		}
		if (flag==1)
		{
			printf("Max Heap\n");
		}
		if (flag==-1)
		{
			printf("Min Heap\n");
		}
		postorder(0);
		printf("\n");
		key=0;
	}
	return 0;
}