Implement your own array-based min-heap of int values (use an ArrayList<Integer> as the array; do not use java.util.PriorityQueue) and drive it with commands.
Input. The first line holds q, the number of commands. Each of the next q lines is one command:
| Command | Effect | Output |
|---|---|---|
insert x |
add x (append, then sift up) | nothing |
remove |
remove and print the minimum (move the last element to the root, then sift down) | the value, or EMPTY |
peek |
print the minimum without removing it | the value, or EMPTY |
size |
the number of elements | |
print |
print the internal array in index order | e.g. [1, 3, 2], or [] when empty |
Duplicates are allowed. To make the internal array deterministic:
- sift-up stops as soon as the parent is ≤ the moving value;
- sift-down stops as soon as the moving value is ≤ its smaller child, and when both children are equal it swaps with the left one.
Example.
Input:
9
insert 5
insert 3
insert 8
insert 1
insert 9
print
peek
remove
print
Output:
[1, 3, 8, 5, 9]
1
1
[3, 5, 8, 9]