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.