Background

Description

1. 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.
2. 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.
3. Write Proj5.C. It will validate command line arguments, read commands from a command file, and print the results of executing commands.
4. 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.

The Command Line

The Command File

• 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

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.

• 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

Submit Tools

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

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.