4373. 堆的基本操作

【题目描述】

堆(Heap)是一种数据结构，有很多类，例如二叉堆、斐波那契堆、二项式堆等，一般说的堆都指二叉堆。

二叉堆一般用一维数组作为存储结构，即按照完全二叉树的编号方式，将对应结点存储在数组对应下标的位置上。

现在请你编程实现一个最小堆，假定堆大小最大为20。

【输入格式】

第一行一个整数$n(1\leq n\leq 20)$，表示堆的初始大小。

接下来一行有$n$个整数表示堆中的初始元素，你要利用这些元素进行下沉建堆。

下来一行一个整数$q(1\leq q\leq 200)$，表示堆的相关操作。

对于每一个操作，首先输入一个整数$op$表示操作类型：

$op=1$，表示进行入堆操作，紧接着输入一个整数$x$，表示要入堆的数；$op=2$，表示进行删除堆顶操作；$op=3$，表示获取堆顶操作；$op=4$，表示打印堆内所有元素。

【输出格式】

对于入堆操作，如果堆满，则输出heap out，否则不需要输出信息。

对于删除堆顶操作，如果堆空，则输出heap empty，否则不需要输出任何信息。

对于查看堆顶操作，如果堆空，则输出heap empty，否则输出当前堆的堆顶。

对于打印堆元素操作，第一行输出一个整数表示堆当前大小，接下来一行按照数组下标从$1\sim n$的顺序输出堆内元素。

注：为了保证结果唯一，在进行下沉操作时，如果左右孩子(如果存在)权值相同且比双亲结点权值小，则向左孩子下沉。

【样例输入】

8
3 1 9 4 5 8 3 2
5
4
3
2
1 2
4

【样例输出】

8
1 2 3 3 5 8 9 4
1
8
2 2 3 3 5 8 9 4

【样例说明】

首先需要下沉建堆，接下来共有5次操作。

第1次是打印堆元素，第2次是查看堆顶，第3次是删除堆顶，第4次是将元素2入堆，第5次是打印堆元素。

【来源】