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.

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


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.