THINK FIRST·CODE LATER

← All labs

One heap class for every order

Problem

In ComparatorHeap, write a generic class Heap<E> (on an ArrayList<E>) whose order is given by a Comparator passed to the constructor: the element that the comparator considers the smallest is at the root. Methods: add (sift up), remove (sift down; returns null when empty), peek, size, toString (the array).

With the right comparator the same class is a min-heap, a max-heap or anything else. The first word of the input chooses the order of a heap of words: min (alphabetical), max (reverse alphabetical) or length (shortest first, then alphabetical). Then come the commands add w, remove, peek, show. At the end, empty the heap. For the input

min
add pear
add fig
add banana
show
peek
add apple
remove
show

the program prints

array: [banana, pear, fig]
at the root: banana
removed apple
array: [banana, pear, fig]
Emptying the heap (min): banana fig pear

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-8-data-1.txt

min
add pear
add fig
add banana
show
peek
add apple
remove
show
What your program must print for d11-8-data-1.txt
array: [banana, pear, fig]
at the root: banana
removed apple
array: [banana, pear, fig]
Emptying the heap (min): banana fig pear

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-8-data-1.txt

Windows PowerShell does not understand <:

Get-Content d11-8-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.