The textbook discusses priority queues in section 6.9. This assignment is related to exercises 6.26 and 6.27 in your textbook.
Create a class PriorityIntQSorted with methods (as outlined in section 6.9 of your textbook) findMin, deleteMin, insert. Both findMin and deleteMin should return the smallest value in the priority queue. (You can infer this from the use of a println statement in line 10 of Figure 6.41 in the textbook.) You'll also need to provide an isEmpty method. The class should be based upon an array of Integers that is kept sorted. (So as elements are added or deleted to/from the priority queue, the elements in the underlying array may have to be shifted to make room, or to keep elements contiguous.)
Your class doesn't need to implement an interface or extend a class. That said, note this from pg. 275 of the text: "Thus, insert, findMin, and deleteMin are expressed as calls to add, element, and remove." In other words, deleteMin() should probably be something like:
public Integer deleteMin() {
return remove();
}
You significant code, then, is in the definition of remove. The situations for the other four methods are analogous.
Test your implementation using the driver PriorityIntQDemo.java. Note that the driver uses the Collection interface's nomenclature for the methods: you'll have to provide an add and remove method that are adapters for insert, and for deleteMin. (You may want to review the discussion of the adapter pattern in section 4.6.4 of the textbook.)
Create a generic class PriorityQSorted that is similar to PriorityIntQSorted, but which is generic. Test using the driver PriorityQDemo.java. Check out Weiss' examples from sections 4.7.1-4 in the text. (The code for findMax can be found in GenericFindMaxDemo.java.) You might also want to peek at Weiss's implementation of a stack in Chapter 16, and his ArrayStack.java.
The primary complication with this implementation is that you are using an array to implement the priority queue, but you can't declare an array of a generic type. For example, this code will not compile (see pg. 155, "generic array objects", for an explanation):
public class C<AnyType>{
private AnyType[] arr = new AnyType[10];
You'll need a way to compare the elements in your array to maintain sorted order. To do this you'll want to use a call to compareTo. To do that you'll need cast operators of the form (Comparable X). The compiler may complain about an "unchecked cast" at this line, because the compiler doesn't know that the data type of X is actually Comparable, since all the compiler will know about X is that it is of type AnyType. This is okay for now.
Create a generic class PriorityQUnsorted that is similar to PriorityQSorted, but which is based on an underlying unsorted array. Note that this will require that you modify the findMin, deleteMin, and insert methods. insert should always place the new elements at the end of the array (in the leftmost empty slot), while deleteMinmay require shifting the array elements to "fill in" the empty space. Test using the driver PriorityQUnsortedDemo.java.
All three of your classes should implement/override the String toString() method. This should display the contents of the array used to implement the class, listed in order from element [0],[1], etc.