CMSC-341 Fall 2003
Project 5
Assigned |
24 Nov 2003 |
Due |
8 Dec 2003 |
Background
This project will give you experience working with heaps. In
particular, you will implement a data structure called a Min-Max Heap
that makes it possible to find both the minimum and maximum elements
in constant time. All other basic operations are O(lgN), and a
Min-Max Heap can be built in O(N) time. You will also read the
original paper that introduced this data structure.
Description
You will implement a Min-Max Heap using Weiss' code as a starting
point. Recall that the implementation in the text is for a Min Heap.
Here are your tasks:
- Obtain these files:
- BinaryHeap.C
- BinaryHeap.H
- TestBinaryHeap.C (if you want it)
- dsexceptions.H
- MinMax.pdf
from this location: /afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj5/.
The file MinMax.pdf is the original paper that introduced MinMax
heaps. It contains a good description of their functionality, as well
as pseudo-code that you can use when implementing your own
routines.
- Modify Weiss' code as described below so that it supports both
findMin and findMax in constant time, and deleteMin and deleteMax in
O(lgN) time.
- Write Proj5.C. It will validate command line arguments, read commands
from a command file, and print the results of executing commands.
-
Answer the questions posed in 341-Fall03-proj5_questions.txt. Copy the
file
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj4/341-Fall03-p5_questions.txt
to your own directory and edit it to provide your answers to the questions.
Don't forget to submit the edited file; it's 10% of this project's
grade.
Below is a detailed discussion of how to implement this project.
The Command Line
Project 5 will be invoked with a command line that consists of one
argument - the name of a command file. Your program should validate the
command line, ensure that the specified file can be opened, then read and
process each of the commands in the file. The commands will specify
operations to be performed on an initially empty Min-Max Heap.
The Command File
The command file format is as follows:
- INSERT X -- Insert the integer X into the heap.
- MIN -- Print the minimum value in the heap and remove it from the
heap.
- MAX -- Print the maximum value in the heap and remove it from the
heap.
- PRINT -- Print the contents of the heap by simply printing each
element of the underlying array on a single line, starting with the
root (i.e. the element at array index 1).
Implementation Details
Recall that a Min Heap has two properties - a structural property and
an ordering property. The structural property is that the heap is
represented as a complete binary tree. The ordering property is that
the values of the children of any node are not less than the node's
value.
To insert the number X into a Min Heap you add X to the tree in the
next open leaf position and restore the heap order property by
percolating up. That is, you repeatedly swap X with its parent's
value while X is less than the parent's value.
To delete the minimum value from a Min Heap you replace the root value
with the value of the last leaf, X, remove that leaf, and percolate
down. That is, you repeatedly swap X with the smaller of the values
of its two children while one of them is smaller than X.
A Max Heap has the same structural property, but the ordering property
is different. In a Max Heap, the values of the children of any node
are not larger than the node's value. To insert value X into a Max
Heap you add it at the next open leaf position and percolate up,
swapping while X is larger than the parent's value. To deleteMax you
replace the root with the value in the last leaf position, X, and
percolate down, swapping with the larger of the values of the children
while one of them is larger than X.
A Min-Max Heap has the same structural property. The ordering property
is a little different. Suppose the root is at level zero. The values
stored at even levels, which are min levels, are less than or equal to
the values of their children. The values stored at odd levels, which
are max levels, are greater than or equal to the values of their
children.
When percolating up or down, you need to know what kind of level you
are on (a min level or a max level) to know what to do. Rather than
looking at just the children and parents of a node, you will need to
look at grandchildren and grandparents. Note that the grandchildren
of the node at index I are at indices 4I, 4I+1, 4I+2, and 4I+3. The
grandparent of the node at index I is at floor(I/4).
You will need to make the following modifications to Weiss' code:
- Write method percolateUp(int i) that figures out whether i is on a
min or max level and calls percolateUpMax(int i) or percolateUpMin(int
i) as appropriate.
- Write percolateUpMin(int i) for percolating up from min levels.
- Write percolateUpMax(int i) for percolating up from max levels.
- Write method percolateDown(int i) that figures out whether i is on a
min or max level and calls percolateDownMax(int i) or percolateDownMin(int
i) as appropriate.
- Write percolateDownMin(int i) for percolating down from min levels.
- Write percolateDownMax(int i) for percolating down from max
levels.
- Write method deleteMax(). Note that the maximum value in the heap
will be one of the two children of the root.
You can find pseudo-code for all of these routines in the PDF file
described above. Note that the routine names used in the PDF file are
different from those given in the list above. You can call your
routines whatever you want (within reason). To help you map from
routine names above and names in the paper:
- The paper has pseudo-code for percolateDown on page 997, but it
calls this routine TrickleDown. TrickleDownMax on the same page is
your percolateDownMax routine. Also, note that the paper says "the
procedure TrickleDownMax is the same except that the relational
operators are reversed". That means that less-than is replaced with
greater-than, and vice versa.
- Routines BubbleUp and BubbleUpMin on page 998 are the ones you
should implement and call percolateUp and percolateUpMin. Again,
percolateUpMax is the same as percolateUpMin except the relational
operators are reversed.
Files To Be Submitted
You should submit all files needed to build your program and the file
containing your answers to the questions.
Submit Tools
There are a number of tools available to you to check on your submittal.
It is your responsibility to ensure that the submittal is correct and will
result in a successful
compilation of your project. Do not wait till the last minute to submit
your files. Give yourself enough time to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit
for it. Why throw away all that hard work you did to write the project?
Check your
submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/ and are
named submitmake and submitrun. You can
use these programs to
make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj5
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o and ii_files),
but leaves the
executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341Proj5 checkers checkfile.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Grading and Academic Integrity
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Your answers to 341-Fall03-proj5_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after midnight of the
due date will not be accepted. Do not submit any files after that time.