3307 - 小根堆建堆(模板3)

通过次数

1

提交次数

1

时间限制 : 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