In this lab assignment you will be implementing the HeapPriorityQueue shown in i

Question

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 <Integer, String>

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

Explanation / Answer

Hi,

Please find the interface implementation class methods of HeapPriorityQueue in java......

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.*;

public class HeapPriorityQueue<K,V> {

protected ArrayList<Entry<K,V>> heap;

protected Comparator<K> comp;

protected static class MyEntry<K,V> implements Entry<K,V> {

protected K key;

protected V value;

public MyEntry(K k, V v) {key = k; value = v;}

public K getKey() {return key;}

public V getValue() {return value;}

public String toString() {return "(" + key + "," + value + ")";}

}

public HeapPriorityQueue() {

heap = new ArrayList<Entry<K,V>>();

heap.add(new MyEntry(null,null));

comp = new DefaultComparator<K>();

}

public HeapPriorityQueue(Comparator<K> c) {

heap = new ArrayList<Entry<K,V>>();

heap.add(new MyEntry(null,null));

comp = c;

}

public int size() {return heap.size() - 1;}

public boolean isEmpty() {return size() == 0; }

public Entry<K,V> min() throws EmptyPriorityQueueException {

if (isEmpty())

throw new EmptyPriorityQueueException("Priority Queue is Empty");

return heap.get(1);

}

public Entry<K,V> insert(K k, V v) {

Entry<K,V> entry = new MyEntry<K,V>(k,v);

heap.add(entry);

upHeap(size());

return entry;

}

public Entry<K,V> removeMin() throws EmptyPriorityQueueException {

if (isEmpty())

throw new EmptyPriorityQueueException("Priority Queue is Empty");

if (size() == 1)

return heap.remove(1);

Entry<K,V> min = heap.get(1);

heap.set(1, heap.remove(size()));

downHeap(1);

return min;

}

public V replaceValue(Entry<K,V> e, V v) {

// replace the value field of entry e in the priority

// queue with the given value v, and return the old value

}

public K replaceKey(Entry<K,V> e, K k) {

// replace the key field of entry e in the priority

// queue with the given key k, and return the old key

}

public Entry<K,V> remove(Entry<K,V> e) {

// remove entry e from priority queue and return it

}

protected void upHeap(int i) {

while (i > 1) {

if (comp.compare(heap.get(i/2).getKey(), heap.get(i).getKey()) <= 0)

break;

swap(i/2,i);

i = i/2;

}

}

protected void downHeap(int i) {

int size = size();

int smallerChild;

while (size >= 2*i) {

smallerChild = 2*i;

if ( size >= 2*i + 1)

if (comp.compare(heap.get(2*i + 1).getKey(), heap.get(2*i).getKey()) < 0)

smallerChild = 2*i+1;

if (comp.compare(heap.get(i).getKey(), heap.get(smallerChild).getKey()) <= 0)

break;

swap(i, smallerChild);

i = smallerChild;

}

}

protected void swap(int j, int i) {

Entry<K,V> temp;

temp = heap.get(j);

heap.set(j, heap.get(i));

heap.set(i, temp);

}

public String toString() {

return heap.toString();

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.