代写数据结构中的Priority Queue以及Binary Heap.
Overview
You are going to build in Java a Priority Queue (PrQUE) ADT in Java. It will be done by building a minimum binary heap (BHEAP) with the 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).
Now that we have established that we are using a heap to produce a priority queue, don’t worry about the various namings we use in the code (which may mix up a bit the technical difference between PrQUE and BHEAP).
What to Hand-in
Hand in your code as per the instructions under Assignment 3 in Sakai.
Interfaces
For uniformity, to aid grading, you must write your program with these specific structures. Note that this time there are interfaces for both MinBinHeap and for EntryPair
Interface Heap_Interface
1 | package MinBinHeap_A3; |
Interface EntryPair_Interface
1 | package MinBinHeap_A3; |
Classes
Class MinBinHeap
1 | package MinBinHeap_A3; |
Class EntryPair
1 | package MinBinHeap_A3; |
Class MinBinHeap_Playground
1 | package MinBinHeap_A3; |
Class RunTests
1 | package MinBinHeap_A3; |
Notes on Operations
insert
Ordering is done based on the integer priorities in the elements that are inserted. Ignore the string for ordering. In the test data we use, the integer priorities in the elements will be unique – there will be no duplicate priorities.
getMin
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.
delMin
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.
build
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 heap that contains exactly those input elements. This means when done the heap will have both a proper structure 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, then bubbling up as needed.
size
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.
Testing and Output
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 use the “print” capability provided (and potentially expand on it) to test your code beyond the scope of the oracle.
Furthermore, please note that just because the Oracle gives you 100, you are not guaranteed any specific grade on the assignment. We do try to put as many things as we can in there edge-case wise, but testing your programs is your responsibility. The main goal of the Oracle is to provide some direction. However, it is not the end-all be-all determiner of correctness. Please do not use this tool as a crutch.