THINK FIRST·CODE LATER

← All labs

A command-driven min-heap

Problem

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]

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d11-1-data-1.txt

9
insert 5
insert 3
insert 8
insert 1
insert 9
print
peek
remove
print
What your program must print for d11-1-data-1.txt
[1, 3, 8, 5, 9]
1
1
[3, 5, 8, 9]

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d11-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content d11-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.