UNC-CH COMP 410

Binary Heap and Priority Queue Implementation

Overview

You are going to 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 (as we have done in class) your heap will allow manipulation of more information. We represent this as a integer (for priority queue position) and a string (associated information). As elements move around in the heap, keep the associated information associated. You design how to do this.

    Example:

                   [4:goheels]
                   /         \
                  /           \
                 /             \
       [9:virginia]           [12:wake]
          /   \                  /
         /     \                /
        /       \              /
   [17:duke]  [11:state]    [23:pitt]

Your 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, your 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

Your 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:

first read in all the command line parameters and save the information (in arrays for example)
create a BHEAP object.
do an insert operation into the BHEAP for each input pair
do a single print operation; this will show the structure of the heap after all the inserts are done; use this format:
```
   3:miller, 7:smith, 9:wilson, 21:adams, 13:davis, 34:carson, 17:jones 
```
create a new empty heap
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.
do a single print operation; this will show the structure of the heap after the direct build is done; use this format:
```
   3:miller, 7:smith, 9:wilson, 21:adams, 13:davis, 34:carson, 17:jones 
```
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:carson
```

What to Hand-in

Hand in your code as per the instructions under Assignment 5 "Binary Heap" in the WorkBase.

Submit a single text file with the entire Java source... main class, any supporting classes, as well as your BHEAP class(es). We should be able to cut and paste this single Java source into a Java IDE and have it compile, execute, and produce your output for grading.

Please check this. Copy your submission once submitted and paste it back into your Java IDE and see if it compiles as a single file. Many of yours are not, due to small things... like multiple includes in wrong places, or "public" being before "class" for the classes after the main in the one file. They are also not compiling due to "package" designations that may not work properly in the environment we use.