#C14123. Min Heap Operations

    ID: 43738 Type: Default 1000ms 256MiB

Min Heap Operations

Min Heap Operations

You are given a sequence of operations to perform on a min-heap data structure. The min-heap supports the following operations:

  • insert x: Insert an integer x into the heap.
  • removeMin: Remove and return the smallest integer from the heap. If the heap is empty, output None.
  • getMin: Return the smallest integer without removing it from the heap. If the heap is empty, output None.
  • size: Return the current number of elements in the heap.

Time Complexity: The operations have the following expected time complexities:
insert: \(O(\log n)\), removeMin: \(O(\log n)\), getMin: \(O(1)\), and size: \(O(1)\).

Your task is to implement the heap such that it reads the list of commands from the standard input and produces the required outputs to the standard output.

inputFormat

The first line contains an integer Q (\(Q \ge 1\)) denoting the number of operations. Each of the following Q lines contains one operation, which can be one of the following forms:

insert x
removeMin
getMin
size

Here, x is an integer.

outputFormat

For each operation of type removeMin, getMin, or size, output the result on a new line. For operations on an empty heap where a minimum is requested or removed, output None.

## sample
5
insert 5
insert 3
getMin
removeMin
getMin
3

5

</p>