Data Structures Homework 4, Fall 1999

Due: Friday, Oct 15, 1999, 12 PM (noon) Using Turnin

In this project, you will construct an implementation of the Priority Queue interface using a heap. You will then use the heap methods to implement the unchecked list from your previous assignment. Instructions on files to submit will be made available with turnin instructions. DO NOT CHANGE ANY OF THE INTERFACES/ ABSTRACT CLASSES I GIVE YOU. If your program does not compile with these interfaces/abstract classes, the TAs/I will not be responsible for it. Your heap data structure should be built using the binary tree interface, and this interface should be implemented using a doubly linked structure. The homework closely follows description of these data structures in your textbook.

This assignment involves you writing the following classes:

• HeapPriorityQueue, which uses a heap to implement the priority queue ADT using a binary tree.
• LinkedBinaryTree, which implements the binary tree ADT using a linked structure.
• Your unchecked list class from previous assignment rewritten to use your heap methods.

The following files will be useful.

• BinaryTree.java (A Simple Binary Tree Interface)
• Container.java
• InvalidPositionException.java
• Item.java
• Node.java
• IntegerComparator.java
• Position.java
• driver.java (This shows you how the LinkedBinaryTree works).
• PriorityQueue.java (A Priority Queue Interface)