Take-home exam: “HeapDemo”

Tuesday, November 5, 2002
Due: Tuesday, November 12, 2002

Ground rules

This is an exam; don't collaborate.

You may use and modify any sample solutions or other pieces of code that have been posted in this course. Likely useful pieces are the tree-drawing function in ~karl/public_html/2270.fall02/rBinSearchTrees/BinTreeNode.cxx and the subscript operator in ~karl/public_html/2270.fall02/HeapDemo/subscript.cxx.

You may not use any other sources of code.

Description

Create a demo of a priority queue.

Details

Do a pointer-based (i.e., tree) implementation; not an array. Use int as the data type of the items in the queue.

Use this menu:

 i 14 : insert 14          
 r: remove the top entry 
 0: reset to empty tree 
 q: exit

Show not only the resulting queue after each insertion or deletion but show the intermediate steps, each triggered by the user hitting the Enter key. (A call to getchar () does the trick).

Use colored nodes to help the user track the changes. You can do this by having

color = CDraw::randomLightColor ();

in the constructor where color is of type int and then use that variable in the drawing like

CDraw::setColor (color);

Files to turn in

Turn in three files: heapdemo.cxx, heap.cxx, and heap.h. (This does not keep you from having more than one class. E.g., if you use two classes, Heap and HeapNode, which is a natural thing to do, you can put both class definitions into heap.h and their implementations into heap.cxx.)

Make your program work with this makefile: ~karl/public_html/2270.fall02/HeapDemo/Makefile.

Previous page | Next page | Back to top

3:40 PM, Thursday, December 12, 2002