CSE373 Data Structures Au07, Homework 4
Written Problems:
-
B-trees. Given the following parameters:
- 1 Page on disk = 2048 bytes
- Key = 20 bytes
- Pointer = 4 bytes
- Data = 256 bytes per record (includes key)
- N = 1 billion data records
What are the best values for:
What is the maximum number of disk accesses required for retrieving a record:
- 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.
- 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.
- Binomial Queues - Weiss
6.32 (p.242 )
Programming:
Implement a binary heap according to the PriorityQueue interface provided.
Your implementations should automatically grow as necessary. Make a separate
file for your binary heap implementation (BinaryHeap.java). 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. Your implementations of BinaryHeaps 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. The Comparable interface is 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 file BinaryHeap.java electronically
using the turn-in link. Please also print out the file and bring it to class on the due date with your answers to the written problems.
