CSE 100: Data Structures (Autumn 1996)

		Programming Assignment #3
		Comparing binary heap and leftist heap performance
		Due: Wednesday, Nov 13, 1996 11:00 pm

	

In this programming assignment you will implement two versions of
the heap data structure:  An array-based balanced binary heap, and a
pointer-based leftist heap.  Then you will run some experiments
to compare the performance of Insert and Merge operations on
these structures.  

In a file heaps.h, write the class declarations for two classes:

----------------------------------------------------------------------
AHeap:  This class implements an array-based balanced binary heap, as 
discussed in lecture and the notes.  Public member functions include:

AHeap(int n);  // create a binary heap containing an array large enough 
               // to hold n elements; initialize as empty
int DeleteMin();  // delete the min element from the heap and return its value
void Insert(int k);  // insert an element with value k into the heap
void Merge(AHeap& h); // merge heap h into this heap; may wreck h
int IsEmpty();  // return 1 if the heap contains no elements, else 0

----------------------------------------------------------------------
LHeap:  This class implements a pointer-based leftist heap, as 
discussed in lecture and the notes.  Public member functions include:

LHeap();  // create an empty leftist heap
int DeleteMin();  // delete the min element from the heap and return its value
void Insert(int k);  // insert an element with value k into the heap
void Merge(LHeap& h); // merge heap h into this heap; may wreck h
int IsEmpty();  // return 1 if the heap contains no elements, else 0

----------------------------------------------------------------------

Define these member functions (and any other functions you may want)
in a file heaps.C.  Hints:

h1.  Operations Insert and DeleteMin are pretty easy to implement
for AHeaps.  With these, it is easy to implement Merge:  Just
do DeleteMin's on one heap, Inserting into the other.

h2.  Merge is the easiest operation to implement for LHeaps.  Then with
Merge, you can easily implement Insert (create a one-element LHeap,
and merge it in) and DeleteMin (deleting the root creates two leftist
heaps, the left and right subtrees of the root; merge them to create
a new leftist heap).  

h3.  Note that your heaps only have to contain int values; no
templates needed here.  Also, only the member functions listed above
will be called when we test your code for grading, though you may
declare and define others if you want.  (Yes, both AHeap and LHeap
objects will contain dynamic member data, and so destructors, copy
constructors, and overloaded assignment "should" be defined for them.
However we will not check this.)

**********************************************************************
Experiments:

When you get your code debugged, run some experiments to investigate
the relative performance of these data structures under Insert and
Merge operations.  Use the Rand program provided (see Rand.C) to
generate sequences of random integers for insertion.  (It is possible
that these sequences will contain duplicates, so your heaps must be
able to contain and correctly handle duplicate values.)  Start with a
short sequence, and double the sequence length successively to create
a series of data points. (The file example_main.C contains examples of
timing these operations.)

Since the integer sequences are random, you should run several
experiments at each sequence length and average them, to get a good
measure of average-case performance.  Collect your data in tables or
graphs, and write a summary of what you found.

**********************************************************************
Turnin Procedure:

With this assignment, you must BOTH (1) submit your source files
using turnin by the deadline date and time, AND (2) turn in printouts
of your source files and hardcopy of your report of experiments
in lecture on Thursday Nov 14.

PLEASE verify that everything compiles properly with your makefile
before you turnin.

In your turnin package, the only types of files we want are *.C,
*.h, makefile, and any online documentation files.  Please do not turnin
executables, *.o files, or anything ending in ~ or % (i.e. editor
files) and ESPECIALLY don't hand in any core files! 

For this assignment, you are not required to supply user or logic
manuals.  (Your code must still be written with good style, and have
enough internal documentation to make it clearly understandable.)
Instead, you should submit the short report of the experiments you
did.  This report should include tables or graphs that show the time
complexity of your Insert() and Merge() operations for array-based and
leftist heaps, as a function of number of elements N.  It should also
include a written explanation and interpretation of the data (a page
or two in length): how the data was collected, and how it fits (or
doesn't fit) with the theoretical prediction of the performance of
these data structures.

An example main program with some suggested ways to test your program
is also provided in the file public/HW3/example_main.C, along with
source code for the random integer generator, and a Makefile.