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

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

http://www.owlnet.rice.edu/~comp201/07-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/07-spring/lectures/lec34/

Quick link to download the code from last semester's lectures on RAC's: http://www.owlnet.rice.edu/~comp201/07-spring/lectures/lec31/rac/rac.zip

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 2n - 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. 

Note that it is now possible for your RAC to be full, so be sure to implement it accordingly.

Step 2: ArrayPQueueFactory extends AArrayRACFactory {...}

Download the source  code for Heapifier.java and add it to your RAC project.

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:32 CDT

©2007 Stephen Wong and Dung Nguyen