CSE373 Data Structures Sp07, Homework 3

Electronic Turn-in of code due: 11am Wednesday, 5/02/07 using this link.
Written Problems and printout of code due: At the beginning of class, Wednesday, 5/02/07
No late assignments will be accepted.

Written Problems:

Note that while you are not required to show your work for these problems, showing your work may allow partial credit to be awarded.

  1. Leftist Heaps – Show the result of inserting values 1 to 12 in order (i.e. 1 first, then 2 second, then 3 third, etc.) into an initially empty leftist heap. 
  2. Skew Heaps - Show the result of inserting values 1 to 12 in order (i.e. 1 first, then 2 second, then 3 third, etc.) into an initially empty skew heap.
  3. Binomial Queues – Weiss 6.32 (p.242 )

Programming:

Implement a binary heap and a three-heap according to the PriorityQueue interface provided.  Your implementations should automatically grow (if interested you may also make them shrink - this is optional) as necessary.  Make a separate file for your binary heap implementation (BinaryHeap.java) and your three-heap implementation (ThreeHeap.java).  For the ThreeHeap we suggest starting with a copy of your BinaryHeap code and making changes as necessary.  Notes: 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). 

Provided code:

Your priority queue implementations must accept Comparable objects.  Many classes such as String and Integer implement the Comparable interface.  Unlike your stacks implementations for Homework 1 that were hardcoded to use ints, your implementations of the PriorityQueue interface need to use generics.  Your implementations of BinaryHeaps and ThreeHeaps in particular need to use compareTo when comparing elements so the code will work on any Comparable object.  More information about Java's Comparable interface may be found at Sun's website. In addition, you might find this description from cse143 to be useful.  Both generics and the Comparable interface are discussed in section 1.5 of the Weiss text.

We will be testing the code that you submit - so we will expect that you have done the same!

Please submit your files BinaryHeap.java and ThreeHeap.java electronically as individual files (not zipped into one file) using the turn-in link here.  Please also print out these files and bring them to class on the due date with your answers to the written problems.