CS231 lecture notes, Fall 1998
Week 13, Friday

Heap assignment review
----------------------

Two tasks:

1) make the Heap generic

   generic means the class has to be written without reference
   to any object in the client code

   Heap objects:   Heap, HeapNode

   client objects: HeapItem, Student, HuffTree

   Comparable acts as an interface between the client code
   and the Heap implementation.


2) fix the performance problem(s) with the Heap implementation

   You can't invoke rank(), because it traverses the tree,
   and that takes linear time.


Generic-ness
------------

Two ways to make an ADT generic:

1) use an interface (abstract class) to define the characteristics
   that are required for admission to the ADT

2) write the ADT in terms of Objects and typecast everything to
   be an object.

When can you use 2 and when do you have to use 1?

Drawback: both methods only work with object types.  Have to
use wrapper classes to work with primitives.


First part of assignment
------------------------

Generic Lists.  We'll use version 2


Second part of assignment
-------------------------

Heap implementation.