3308 - 大根堆建堆(模板4)
时间限制 : 1 秒
内存限制 : 128 MB
输入一组正整数,运用大根堆排序。 然后再输出一序列的数字,当数字大于0时,采取插入操作,当数字为-1时,进行根节点的删除操作。 比如输入6个数字8 6 2 5 9 4,采用小根堆排序时,排序树为:
9
/ \
8 4
/ \ /
5 6 2
然后我们输入-1 3 7 -1,代表先对堆进行一次删除操作,再插入数字3和7,然后再进行一次删除操作。
删除根节点9之后为:
8
/ \
6 4
/ \
5 2
插入3之后为:
8
/ \
6 4
/ \ /
5 2 3
插入7之后为:
8
/ \
6 7
/ \ / \
5 2 3 4
再次删除根节点8为:
7
/ \
6 4
/ \ /
5 2 3
输出为7 6 4 5 2 3.
输入
第一行输入两个数n和m。 第二行输入n个正整数,用空格隔开。 后面有m行整数,代表插入和删除。
输出
一行数字,代表在剩余的堆中,从根节点开始到叶节点,按层从左到右排序的节点序列。
样例
输入
6 4 8 6 2 5 9 4 -1 3 7 -1
输出
7 6 4 5 2 3