CS 223 Out-lab 1
Week of 1/23

Due: to TA by 2/2

Priority Queues

The goal of this out-lab is to implement a min-priority-queue (see page 138 of CLRS).  Your priority queue class should implement the following four methods: Insert, Minimum, Extract-Min, Decrease-Key.  Note that the book presents pseudocode for a max-priority-queue; you will need to modify this slightly for a min-priority-queue.  Your priority should use a heap as its central data structure.  You may assume that the key values are integers.

Your code should include the following:

• a class called PriQueue.  This class should implement methods for Insert, Minimum and Extract-Min and Decrease-Key.
   
• an interface called QueueElement.  This interface should let different types of objects belong to the queue provided that they implement the QueueElement interface.  The QueueElement interface should have two methods: setKey and getKey
   
• a class called MyElement that implements the QueueElement interface
   
• a driver class.  This should class should create a number of instances of MyElement and test all of the PriQueue methods.

What to Turn In

• a printed copy of all source code.  Ensure the source code is documented.
• a printout of a test run of the driver.