Overview
Build in Java a Binary Heap ADT (BHEAP). You are also going to use your BHEAP to implement and exercise a priority queue.
Instead of a single integer as heap element this heap will allow manipulation of more information. We represent this as an integer (for priority queue position) and a string (associated information). As elements move around in the heap, keep the associated information associated. the design how to do this.

The main method will provide 2 modes of operation: interactive, and command line. Details of each below.
Interface: The BHEAP will provide this collection of operations:
insert
in: the integer priority and associated string information
return: void, boolean, whatever works for you

delMin
in: nothing
return: void, boolean, whatever works for you

getMin
in: nothing
return: both the integer priority and the associated string

size
in: nothing
return: integer 0 or greater

build
in: array of elements that need to be in the heap
return: void, or boolean, or whatever
(assume for a build that the bheap will start empty)

In addition, the program at the driver level will need to do these:
print
in: nothing
side effect: prints, not really a part of the ADT behavior it might be in the BHEAP ADT (thats ok), or you might wish
to return the heap data with some getStuff internal op and
print at the driver level

sort
in: nothing
side effect: does like print, but it generated the elements
in sorted order by calling getMIn and delMin as many times
as there are elements in the heap

new
in: nothing

fill
in: how many randomly generated items to insert, generate
them, call insert for each

build
in: collect information from user and construct array(s), then call
heap build and pass array information

Driver/tester main method
the main class/method will provide two modes of operation:
â€¢ Mode 1: interactive test driver
â€¢ Mode 2: command-line "batch" operation
We discuss the input format and output format for each mode separately below.
How will we know which mode to operate in?
-- If your program is executed with command line args, then operate in mode 2.
-- It is is run with no command line args, then operate interactively in mode 1.

Mode 1: Interactive test driver
This will be like the BST assignment (parts 1,2). You will present the user with a menu of single character operations to select and apply each operation to your BHEAP as directed. Mode 1 will help you debug your code and get the BHEAP working correctly.

Input format

Print a single line showing the user the single letter commands, and wait for keyboard input: command (q,n,i,d,g,s,b,f,p,o)?
Apply the selected operation, produce any output needed, and loop back for another command. Here "q" is quit, "n" is make a new empty BHEAP, "i" is insert, "d" is delete minimum, "g" is get minimum, "s" is for size, "b" is for build, "f" is fill, "p" is print the heap, and "o" is order (sorted) print.

Output format

Make the output look like this:
â€¢ for print:
â€¢ 3:miller, 7:smith, 9:wilson, 21:adams, 13:davis, 34:carson, 17:jones
This is simply the elements in the heap in array subscript order, from 1 (don't print the 0 element).

â€¢ for order (sort) print:
â€¢ 3:miller, 7:smith, 9:wilson, 13:davis, 17:jones, 21:adams, 34:carson
This is like print but the elements are not in heap/array order, they are in sorted order.
â€¢ for getMin:
â€¢ 3:miller
â€¢ for size:
â€¢ 7 elements
â€¢ for insert: ask the user for an integer priority, and a string value, then produce no printed output
â€¢ for delMin: no printed output
â€¢ for build: no printed output
â€¢ for fill: ask user for number of items to generate, then no printed output
â€¢ for new: no printed output

Insert command
Ignore the string for ordering. In the test data we use, the integer priorities will be unique.
For this implementation, handle duplications this way. If you get an element inserted that has the same priority as one already there (same integer) just insert it as the algorithm allows.
Consider this question: lets think of two elements being added, both with priority 3 (let's say). Let's say element E is added first (with integer priority 3) and then later element E' is added (also with priority 3). Also assume we are just construcing the heap in this interval.. no deletes are being done. If we then do a sort/print (that is, begin removing all the elements in priority order with repeated delMin calls) will E thcome out first and E' second, guaranteed? In other words, does our heap algorithm maintain insertion order among elements at the same priority level?

Fill command
Like with the BST code, the fill command will help debug the code without having to type a lot of input. For fill, ask the user how many items to generate. Then generate an integer 0 or greater at random, and also generate a random string (like we did for BST). This will give you two random pieces of data to store in the heap together as one priority queue element. Do the insert command on the each pair as you generate them. Produce no printed output.

Build command
In interactive mode, let's do the build command this way. Go into a loop where you ask the user to give an integer then a string. Store the user input into array(s). Stop when the user gives a "-1" for integer. Then do the build operation with the array(s) created.

Order (sort) print command
The intent is to "sort" by repeatdly doing (getMin,delMin) pairs of operations. This is necessarily destructive to the heap, and when this operation is complete the heap will be empty. This is ok. Implementing the "o" operation this way is fine, and we will live with it leaving up with an empty heap.
If you wish to rebuild the heap so the we see the sorted order but the heap remains when done, that is ok too. One this you can do it create a second heap, and as you do getMin you do an insert in the new heap. You grow the new heap as you diminish the one you are sort/printing. When done, set the new heap to being the "real" heap that the driver is manipulating. Another thing you could do is save the elements as they come out of the heap (in array(s)) and then do a build using the array(s) when the sort/print is finished.

Mode 2: Command-line batch operation
Mode 2 will read data from the command line -- meaning from the (String[ ] args) parameter to "public static void main". It will not be interactive and will only perform some of the BHEAP operations.

Input format
The input will consist of pairs of values, alternating integer and string.
Example:
17 jones 21 adams 3 miller 7 smith 13 davis 34 carson 9 wilson

Operations and Output format
Do the following things in the main class:
1. first read in all the command line parameters and save the information (in arrays for example)
2. create a BHEAP object.
3. do an insert operation into the BHEAP for each input pair
4. do a single print operation; this will show the structure of the heap after all the inserts are done; use this format:
5. 3:miller, 7:smith, 9:wilson, 21:adams, 13:davis, 34:carson, 17:jones
6. create a new empty heap
7. take the saved array(s) of input pairs and do the special direct heap build operation, from the inputs in the order they were given.
8. do a single print operation; this will show the structure of the heap after the direct build is done; use this format:
9. 3:miller, 7:smith, 9:wilson, 21:adams, 13:davis, 34:carson, 17:jones
10. generate a sorted output sequence by doing getMin and then delMin as many times as there are elements in the heap; make all the output appear on a single line, as with print: 3:miller, 7:smith, 9:wilson, 13:davis, 17:jones, 21:adams, 34:carso

Overview Build in Java a Binary Heap ADT (BHEAP). You are also goi...