EECS 380 Homework 4
Winter Semester '01
Assigned Tuesday March 20 2001.
Due Thursday, March 29th, 6pm, EECS 380 box in room 2420 EECS
Update: For part 3 you only need to provide data for N<=20.
Update: For part 2 the `discuss the advantages and disadvantages' was added to the turn-in list.
1. Ternary heaps
You have been exposed to binary heaps in class and in your text. Further, it has
been shown how to use a heap to implement a priority queue.
Implement a priority queue class with the same interface
as priority_queue in STL (you can specialize it to doubles
if you don't feel comfortable with templates), but such that
it uses ternary heaps internally. Feel free to reuse and modify
any code from Sedgewick (although you should comment your code so it is
clear what you have borrowed) and use STL components (classes, functions,
Implement heapsort using priority queues, namely use STL's priority_queue
class (that is based on binary-heap operations) and your own implementation
based on ternary-heap operations. Race the two priority queues against
each other within the context of heapsort. You need to conclude whether
ternary heaps are any better than binary heaps. Supply a plot which shows how
each performs as you vary N. Provide enough data points over a wide enough
range that the general shape of the curves is obvious and so the
relationship between the two heapsorts is obvious. Note: you should not
call the STL's heapsort. Rather use the STL's priority queue to perform a
Discuss the advantages and drawbacks of ternary heaps compared to binary
3. Some math
Say we take an array of size N where the value of each element in the array
is chosen randomly (with a uniform probability over a range large enough
that repeated values are very unlikely). What are the odds that such an
array is in binary heap order? Ternary heap order?
You may answer this question using a number of techniques.
Provide a graph which shows both probabilities displayed out to a value of
20. Figuring out a good way to display this data so that the graph is
informative is a part of the assignment!
- You may
empirically evaluate this number for all values less than or equal to 20 by
randomly producing ``enough'' arrays to be confident that your values for
each `N' is very close.
- You may provide a mathematical formula, with an explanation, which
answers this question for an arbitrary value of N. Ideally this formula
would be a closed form solution. Your explanation must be clear enough
that our graders can understand it.
- You may use some other technique (other than looking it up or asking
someone!) which solves the problem for values less than or equal to 20.
- Your source code for the ternary heap and the priority queue.
- Your code for the heapsort
- The graph showing the speeds of the STL based heapsort and the
- A paragraph or two discussing the advantages and drawbacks of ternary
heaps compared to binary heaps.
- Source code or formula with explanation, or whatever you used to
answer this question.
- A readable graph of the probabilities up to N=20
A ternary heap is one where the heap is implemented on a complete 3-tree (see
page 233 of our text). Remember that complete M-trees can be
implemented fairly easily on an array.