Min Heap — Insert and Extract

Practice this coding question on Coding Gurukul.

Problem statement

Implement a binary min heap using an array. Start empty. - INSERT x: add x. - MIN: print the smallest value without removing it. - EXTRACT: remove and print the smallest value. - SIZE: print the number of values. MIN and EXTRACT print EMPTY when the heap is empty. Keep duplicate values as separate entries. INSERT produces no output. Use O(log q) time for insertion and extraction, and O(1) for MIN and SIZE. Worked example Inserting 7, 2 and 5 makes 2 the minimum. MIN prints 2 and EXTRACT removes and prints 2. MIN then prints 5, and SIZE prints 2.

Input format

First line: q. Next q lines: INSERT x, MIN, EXTRACT, or SIZE.

Output format

One line per MIN, EXTRACT or SIZE.

Constraints

1 <= q <= 100000; -10^9 <= x <= 10^9. At least one output command.

Sample input

7
INSERT 7
INSERT 2
INSERT 5
MIN
EXTRACT
MIN
SIZE

Sample output

2
2
5
2

Sign in to run or submit a solution in C++, Java or Python.