#C14123. Min Heap Operations
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 integerx
into the heap.removeMin
: Remove and return the smallest integer from the heap. If the heap is empty, outputNone
.getMin
: Return the smallest integer without removing it from the heap. If the heap is empty, outputNone
.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
.
5
insert 5
insert 3
getMin
removeMin
getMin
3
5
</p>