Comp202: Principles of Object-Oriented Programming II
Spring 2006 -- Lab #14: Heaps and Priority Queues   

Recall the Restrict Access Container (RAC) from last semester:

http://www.owlnet.rice.edu/~comp201/05-spring/lectures/lec31/

What we did there was to implement RAC using LRStruct.  In particular, for priority queues, we used a sorted LRStruct with a InsertInOrder visitor as insertion strategy:

http://www.owlnet.rice.edu/~comp201/05-spring/lectures/lec31/priority/

The purpose of this lab is to implement a priority RAC using arrays with the heap structure.  We will do this in two steps that mirror the LRStruct implementation of RAC:

1. Create a class called AArrayRACFactory that implements IRACFactory.  This class is to use an array of some fixed size to hold the data.
2. Create a class called ArrayPQueueFactory that extends AArrayRACFactory by implementing the makeRAC() method to manufacture priority queues where the "smallest" object has the highest priority.

Step 0: Test Class

Write stub code for ArrayPQueueFactory  and write a JUnit test for it!  You don't think you can get away without writing test classes, do you?

Step1: Class AArrayRACFactory implements IRACFactory { ...}

Mimic the implementation of ALRSRACFactory done in the Comp201 RAC lecture by defining a protected static class called AArrayContainer that implements IRAContainer by using a protected fixed size array (pick a number of the form 2ⁿ - 1).  ArrayContainer is abstract with two abstract methods: get() and put(...).  For now, the elements(...) method is concrete and just returns the IList containing the elements in the array data store.

Step 2: ArrayPQueueFactory extends AArrayRACFactory {...}

In this class, anonymously extend AArrayContainer by implementing get() and put(...) using the siftup() and siftdown() method of a Heapifier as shown in the lecture.  The makeRAC() method will simply return an instance of this anonymous class.

Last Revised Thursday, 03-Jun-2010 09:52:24 CDT

©2006 Stephen Wong and Dung Nguyen