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, adapters, etc).

2. Heapsort

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 heapsort.

Discuss the advantages and drawbacks of ternary heaps compared to binary heaps.

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.

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.

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!

Turn-in list

- 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 ternary-heap heapsort.
- 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

Terms/hints

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.