CSE 373 Data Structures 09au, Homework 3 (68 points)
Electronic Turn-in due: 11:45pm
Programming (41 points):
Implement three priority queues according to the PriorityQueue interface
provided. You should provide the
- a binary heap
- a three-heap
- another heap
implementation of your choice
Each heap implementation should be in its own file (BinaryHeap.java, ThreeHeap.java, MyHeap.java). Implement the BinaryHeap
(a binary min heap) as discussed in lecture.
For the ThreeHeap we suggest starting with a
copy of your BinaryHeap code and making changes as
necessary. Your ThreeHeap
should still follow the contiguous structure (complete tree) form of the binary
min heap discussed in class. For your third heap
implementation, feel free to get creative.
The simplest possible implementation might just use an array (sorted or
unsorted), a linked list (sorted or unsorted) or a tree. Whatever you do, be sure it implements the PriorityQueue interface
provided, and does not use parts of the Java collections framework. Your priority queues only need to work with
Your implementations should automatically grow (if
interested you may also make them shrink - this is optional) as necessary. Note: Growing an array implementation one
element at a time is not likely to be the most time efficient solution, and you
should NOT use Java class libraries (no import statements).
- PriorityQueue.java - interface that corresponds to a PriorityQueueADT
for doubles. It is for BinaryHeap.java, ThreeHeap.java,
and MyHeap.java code that you must write.
- A helper
We will be testing the code that you submit -
so we will expect that you have done the same!
also be asking you to turn in your testing code.)
Grading: each data structure is worth 11 points, which is total 33 points. Insert(): 4 points, DeleteMin(): 4 points, and isEmpty + makeEmpty(): 3 points. Any mistakes elsewhere like in constructor() could lead points reduction too if it makes these functions not work well. There are another 8 points for style such as no comment, inefficient design, didn't follow the direction (inclduing all codes)..etc.
Write-up Questions (27 points):
This week your write-up involves a comparison of your three
heap implementations. I would expect
these reports to be a couple of pages long, potentially longer if you include
many graphs or tables. Exceptional
reports may be awarded a small amount of extra credit, so have fun with
this! Please prepare a report that
addresses the following:
- Big-O Analysis (8 points): What is the worst case big-O running time of isEmpty, insert, findMin,
and deletemin operations on all three of your
heap implementations (Binary Min Heap, ThreeHeap,
- Timing your code (12 points) : Perform several timing experiments (similar
to what you did in homework #2, where you timed pieces of code), to
examine the running time of all three of your heap implementations. An experiment will include running the same client code (that uses a
Priority Queue) for your three different heap implementations *for several
values of N* and timing this. It is
up to you to write and to determine what this client code should be. Just be sure that it exercises your
insert and deletemin operations “in a
reasonable manner” – reasonable here means eventually deleting
everything that has been inserted into the heap. You are not required to explicitly
measure calls to findMin and isEmpty
but feel free to do so if interested.
Similar to homework #2, graphing your results is recommended, but a
table of results will work also.
- Comparison (5 points): Compare what you see in your experiments, to
what you expected to see based on a big-O analysis. (This is similar to what you should have
done in homework #2 as well.)
In your discussion you should answer these questions:
- How useful was big-O for predicting the measured
run time of insert and deletemin for your three
- (3 points for a and b) If your predictions
based on Big-O differed substantially from your measured times, speculate
as to why this occurred.
- (2 ponits) Which of your three
implementations would you recommend to someone who needs to use a
heap? Why is that one
preferred? Are there any
conditions under which you might suggest using your other
- Testing (2 points) : Please briefly discuss how you went about testing
your three heap implementations.
Feel free to refer to your submitted test files.
What to turn in:
Electronic Turn-in should include the following files:
Electronic version of
your project report in pdf, MS word, or text
format (please check with us first if you need to submit in another
- Any Java files needed
for your three Heap implementations, at least: BinaryHeap.java,
- Java files you used to
test your three implementations.
- Java client code (code
that uses your heap implementations) that you used in your timing
Above and Beyond:
There are no explicit above and
beyond options for this assignment, but exceptional reports may receive small
amounts of extra credit. You might also consider
implementing several different heaps from very simple to very complex (the book
discusses Leftist, Skew, Binomial Queues, and Fibonacci). If you implement other heaps and discuss them
in your report, please include the Java code for those heaps as well. The file named MyHeap.java
is the one that will be graded as part of the original assignment.