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