You are going to build in Java a Binary Heap ADT (BHEAP). It will be a minimum binary heap (numerically smallest priority at the root of the tree).
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. We will do this with a element object that contains both (see Interfaces below).
Example:
[4,goheels]
/ \
/ \
/ \
[9,virginia] [12,wake]
/ \ /
/ \ /
/ \ /
[17,duke] [11,state] [23,pitt]
Hand via Sakai, as per the instructions there.
See the HeapInterface below for instructions on
submitting as an Eclipse project.
For uniformity, to aid grading, you must write your program with these specific structures.
/**
* COMP 410
*
* Make your class and its methods public!
* Don't modify this file!
* Submission directions: Zip your eclipse project folder
* (e.g. Assignment5) for this assignment and upload it to Sakai.
* That folder should contain src and bin folders with
* your code/classes.
*
* Begin by creating a class that implements this interface.
*
*/
public interface HeapInterface {
/*
Interface: The BHEAP will provide this collection of operations:
insert
in: an EntryPair object, containing the priority and string
return: void
delMin
in: nothing
return: void
getMin
in: nothing
return: an element (an EntryPair object)
size
in: nothing
return: integer 0 or greater
build
in: array of elements that need to be in the heap
return: void
(assume for a build that the bheap will start empty)
*/
// ADT operations
void insert(EntryPair entry);
void delMin();
EntryPair getMin();
int size();
void build(EntryPair [] entries);
}
public class MinBinHeap implements HeapInterface {
// in here go all your data and methods for the heap
public MinBinHeap ( ) { // default constructor
// explicitly include this
// we need to have the default constructor
// if you then write others, this one will still be there
}
}
/**
* COMP 410
*
* this is complete code, with
* getters and setters for the fields in an element
* you should not need to add any code to it
*/
public class EntryPair {
public String value;
public int priority;
public EntryPair(String aValue, int aPriority) {
// variables set when object is created
value=aValue;
priority=aPriority;
}
public EntryPair() {
// default constructor, must set variables
// after creating object using setters or directly
}
public String getValue() { return value; }
public int getPriority() { return priority; }
public void setValue(String aValue) { value=aValue; }
public void setPriority(int aPriority) { priority=aPriority; }
}
public class AssnBHeap {
public static void main (String[] args) {
// your code to create and exercise a min bin heap
// thorough testing is your responsibility
// you may wish to create an interactive driver
// like we did for BST/SPLT
// you may wish to create methods like
// -- print
// -- sort
// -- random fill
// -- etc.
// in order to convince yourself your code
// is doing the right thing
}
// anything else you need to add in
}
Ordering is done based on the interger priorities in the elements that are inserted. Ignore the string for ordering. In the test data we use, the integer priorities in the elements might not be unique.
For this implementation, handle priority 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 in the text does. This means, place it in the first open slot in the array, and bubble it up towards the root until it finds a spot where it's parent priority is not larger.
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 come out first and E' second, guaranteed? In other words, does our heap algorithm maintain insertion order among elements at the same priority level?
This operation returns an element (the entire object, priority and data value). It does NOT alter the heap. The heap has the same elements in the same arrangement after as it did before. If getMin is done on an empty heap, return null.
This operation removes the root element (the entire object) from the heap. The size of the heap goes down by 1 (if the heap was not already empty). If delMin is done on an empty heap, treat it as a no-op... i.e., do nothing other than return void.
The build operation should start with an empty heap. It receives an array of element objects as input. The effect is to produce a valid head that contains exactly those input elements. This means when done the heap will have both a proper strcuture and will exhibit heap order.
Build is not the same as doing an insert for every element in the array. It is the special O(N) operation from the text (and shown in class) that starts with placing all elements into the heap array with no regard to heap order.
The size operation simply returns the count of how many elements are in the heap. It should be 0 if the heap is empty, and always return a 0 or greater.
For testing, use the animation page given in class to get test cases and examples of correct behavior. Make sure your code is doing the same.
Their is no specific output or format required for this assignment. We assume you will create some "print" capability that will assist you in seeing how your code is working.
For grading, we will have our own "main" that will create instances of the class MinBinHeap and exercise those objects. We will be able to directly examine and manipulate the objects you have created. For this to happen correctly, you must write your code to the specs given in the "Interfaces" section. If you do not, the program will be returned ungraded for you to correct.