In this lab assignment you will be implementing the HeapPriorityQueue shown in in code fragments 9.8 and 9.9.

Similar to your implementation of the LinkedBinaryTree in a previous lab, you will need implement all the interfaces and class that the HeapPriorityQueue builds on in order to get your project to compile.

For this assignment you may import the following classes from the java class libraries:

java.util.Comparator (we will explore the Comparator later)

java.util.ArrayList (the textbook ArrayList will not work in this project)

Warnings:

Some of the needed interfaces and classes may not be formal code fragments. You may need to develop your own classes based on the descriptions in the textbook.

Do a good job, you will be using your HeapPriorityQueue in the next assignment.

In completing this assignment, you must include and use the interfaces and classes presented in the textbook.

A large part of this exercise will be gathering together the various code fragments and placing them in the right classes.

Once you have successfully implement the HeapPriorityQueue class:

Create a client class that does the following:

Creates an instance of a HeapPriorityQueue for an entry type of

Add the following entries to the queue

( 7, seven )

( 5, five )

( 1, one )

Use a while queue not empty loop to remove and display lowest priority item from the queue on each removal.

Example output:

===== Adding entries to queue =====

Inserting entry ( 7, seven )

Inserting entry ( 5, five )

Inserting entry ( 1, one )

===== Removing entries from queue =====

removeMin() returns entry ( 1, one )

removeMin() returns entry ( 5, five )

removeMin() returns entry ( 7, seven )

I just need the Client class

The book is

Data Structures and Algorithms in Java Sixth Edition

Michael T. Goodrich Department of Computer Science University of California

Irvine Roberto Tamassia Department of Computer Science Brown University

Michael H. Goldwasser Department of Mathematics and Computer Science Saint Louis University