The first solution should be a typical one. It uses the normal interface and holds Objects to be generic. It uses a Vector to hold (object,priority) pairs. The only substantial difference from the common student solutions is that this implementation keeps the vector unsorted, and scans it on Remove operations.
The second solution (chronologically the first) uses some more Java tricks. It implements two different Insert operations, one normal and the other takes objects which implement a Prioritized interface that allows the object to compute its own priority. It also rolls the test code into the PriorityQueue class.