C1100 - 二叉堆实现的优先队列
题目描述
小明刚学过使用二叉堆的方式去实现优先队列，现在给出一组无序的整数数组，请使用二叉堆的方式去实现优先队列（数值越大优先级越高，大顶堆），然后根据特定的命令输出对应的数据
构建优先队列（大顶堆）的过程是：
从最后一个非叶子节点到根节点开始进行下沉操作，下沉操作是：当前节点与左右孩子比较，如果比孩子大，则已调整为堆，则停止下沉；如果比孩子小，则与较大的孩子交换，交换到新的位置后，继续向下比较，一直比较到叶子节点
比如输入的数据是：
10
4 1 3 2 16 9 10 14 8 7
构建大顶堆的过程是：
构建完成优先队列（大顶堆）后，根据命令进行输出：
getTop：输出优先队列的队首元素
show：输出优先队列（大顶堆）的每个节点的值，从1到n号节点的值，使用空格分隔，注意不是出队列，只是输出二叉堆中的节点数据
pop：弹出队首元素
push x：将x入队到优先队列中
这里的pop操作过程是：
将二叉堆的堆顶元素出队后，然后将二叉堆最后一个的节点放到堆顶，接着从堆顶开始执行下沉操作，就可以实现pop之后还是一个有效的优先队列了（大顶堆）
push x的操作过程是：
将x放入到二叉堆的最后一个节点的之后（也就是成为最后一个节点），然后对x节点执行上浮操作，即可调整为有效的优先队列（大顶堆）
上浮操作为：新节点与双亲节点比较，如果小于等于双亲，则已经调整为堆，则停止上浮；如果比双亲大，则与双亲交换，交换到新的位置后，继续向上比较，从叶子一直比较到根
输入格式
第1行：一个整数n，代表初始的无序整数的个数
第2行：n个空格隔开的整数
第3行：一个正整数m，代表接下来有m条命令
接下来m行，是m行命令：每个命令占1行
输出格式
根据命令输出对应的结果，有输出结果的命令输出内容独占一行，对于所有命令，保证至少有一条输出
show命令：输出构建的大顶堆的每个节点的值，从1到n号节点的值，使用空格分隔，如果队列为空，则什么也不做
getTop命令：输出堆顶节点的值，如果队列为空，则什么也不做
pop命令：出队队首元素（即弹出堆顶节点），不需要有输出，但要保证pop之后还是一个大顶堆，需要进行调整，如果队列为空，则什么也不做
push x命令：将x入队到优先队列中，不需要有输出，但要保证push x之后还是一个大顶堆，需要进行调整
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 10 4 1 3 2 16 9 10 14 8 7 7 show getTop pop show push 100 getTop show |
16 14 10 8 7 9 3 2 4 1 16 14 8 10 4 7 9 3 2 1 100 100 14 10 4 8 9 3 2 1 7 |
数据范围与提示
100%的数据：$1 \le n \le 250$，$2 \le m \le 100$，每个节点的值在int取值范围内
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式