سؤال
I have a homework problem as follows:
Created HeapPriorityQueue that will implement Priority queue
https://stackoverflow.com/questions/18683764
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianimport java.util.Arrays;
public class HeapPriorityQueue<K,V extends Comparable<K>> implements PriorityQueue<K, V> {
private static final int DEFAULT_CAPACITY = 10;
protected K[] array;
protected int size;
/**
* Constructs a new BinaryHeap.
*/
@SuppressWarnings("unchecked")
public HeapPriorityQueue() {
// Java doesn't allow construction of arrays of placeholder data types
array = (K[])new Comparable[DEFAULT_CAPACITY];
size = 0;
}
/**
* Adds a value to the min-heap.
*/
public void add(K value) {
// grow array if needed
if (size >= array.length - 1) {
array = this.resize();
}
// place element into heap at bottom
size++;
int index = size;
array[index] = value;
bubbleUp();
}
/**
* Returns true if the heap has no elements; false otherwise.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns (but does not remove) the minimum element in the heap.
*/
public K peek() {
if (this.isEmpty()) {
throw new InvalidKeyException("Invalid Key");
}
return array[1];
}
/**
* Removes and returns the minimum element in the heap.
*/
public K remove() {
// what do want return?
K result = peek();
// get rid of the last leaf/decrement
array[1] = array[size];
array[size] = null;
size--;
bubbleDown();
return result;
}
/**
* Returns a String representation of BinaryHeap with values stored with
* heap structure and order properties.
*/
public String toString() {
return Arrays.toString(array);
}
/**
* Performs the "bubble down" operation to place the element that is at the
* root of the heap in its correct place so that the heap maintains the
* min-heap order property.
*/
protected void bubbleDown() {
int index = 1;
// bubble down
while (hasLeftChild(index)) {
// which of my children is smaller?
int smallerChild = leftIndex(index);
// bubble with the smaller child, if I have a smaller child
if (hasRightChild(index)
&& array[leftIndex(index)].compareTo(array[rightIndex(index)]) > 0) {
smallerChild = rightIndex(index);
}
if (array[index].compareTo(array[smallerChild]) > 0) {
swap(index, smallerChild);
} else {
// otherwise, get outta here!
break;
}
// make sure to update loop counter/index of where last el is put
index = smallerChild;
}
}
/**
* Performs the "bubble up" operation to place a newly inserted element
* (i.e. the element that is at the size index) in its correct place so
* that the heap maintains the min-heap order property.
*/
protected void bubbleUp() {
int index = this.size;
while (hasParent(index)
&& (parent(index).compareTo(array[index]) > 0)) {
// parent/child are out of order; swap them
swap(index, parentIndex(index));
index = parentIndex(index);
}
}
protected boolean hasParent(int i) {
return i > 1;
}
protected int leftIndex(int i) {
return i * 2;
}
protected int rightIndex(int i) {
return i * 2 + 1;
}
protected boolean hasLeftChild(int i) {
return leftIndex(i) <= size;
}
protected boolean hasRightChild(int i) {
return rightIndex(i) <= size;
}
protected K parent(int i) {
return array[parentIndex(i)];
}
protected int parentIndex(int i) {
return i / 2;
}
protected K[] resize() {
return Arrays.copyOf(array, array.length * 2);
}
protected void swap(int index1, int index2) {
K tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public Entry<K, V> max() throws EmptyPriorityQueueException {
// TODO Auto-generated method stub
return null;
}
@Override
public Entry<K, V> insert(K key, V value) throws InvalidKeyException {
// TODO Auto-generated method stub
return null;
}
@Override
public Entry<K, V> extractMax() throws EmptyPriorityQueueException {
// TODO Auto-generated method stub
return null;
}
}
this should implement this PriorityQueue
/**
* Interface for the priority queue ADT
*
* K is the key of the entry stored in the priority queue and denotes the priority of the entry.
*
* V is the auxillary data of the entry
* @author bryann
*
*/
public interface PriorityQueue<K extends Comparable<K>,V> {
/**
* Returns the number of items in the priority queue
*
* @return number of items in the priority queue
*/
public int size();
/**
* Returns whether the priority queue is empty.
*
* @return true if the priority queue is empty. Otherwise, false.
*/
public boolean isEmpty();
/**
* Returns but does not remove an entry with maximum priority key
*
* @return entry that has the highest priority key
* @throws EmptyPriorityQueueException
*/
public Entry<K,V> max() throws EmptyPriorityQueueException;
/**
* Inserts a key-value pair and returns the entry created.
*
* @param key priority key of the entry to be inserted
* @param value value of the entry to be inserted
* @return entry that was inserted into the priority queue
* @throws InvalidKeyException
*/
public Entry<K,V> insert(K key, V value) throws InvalidKeyException;
/**
* Removes and returns an entry with maximum priority key
*
* @return entry that has the highest priority key
* @throws EmptyPriorityQueueException
*/
public Entry<K,V> extractMax() throws EmptyPriorityQueueException;
}
while the Driver class is this
public class HeapPriorityQueueDriver {
public static void main(String[] args) {
PriorityQueue<Integer, String> queue = new HeapPriorityQueue<Integer, String>();
queue.insert(0, "Zero");
queue.insert(10, "Ten");
queue.insert(1, "One");
queue.insert(5, "Five");
queue.insert(3, "Three");
queue.insert(7, "Seven");
queue.insert(9, "Nine");
while(!queue.isEmpty()) {
System.out.println(queue.extractMax());
} // end while
} // end main
}
the problems I get are
Bound mismatch: The type String is not a valid substitute for the bounded parameter <V extends Comparable<K>> of the type HeapPriorityQueue<K,V> HeapPriorityQueueDriver.java /MP7/src/simon/mp7 line 6
Java Problem
Bound mismatch: The type K is not a valid substitute for the bounded parameter <K extends Comparable<K>> of the type Entry<K,V> HeapPriorityQueue.java /MP7/src/simon/mp7 line 199
Java Problem
Bound mismatch: The type K is not a valid substitute for the bounded parameter <K extends Comparable<K>> of the type Entry<K,V> HeapPriorityQueue.java /MP7/src/simon/mp7 line 193
Java Problem
Bound mismatch: The type K is not a valid substitute for the bounded parameter <K extends Comparable<K>> of the type Entry<K,V> HeapPriorityQueue.java /MP7/src/simon/mp7 line 187
Java Problem
The method compareTo(K) is undefined for the type K HeapPriorityQueue.java /MP7/src/simon/mp7 line 126
Java Problem
The method compareTo(K) is undefined for the type K HeapPriorityQueue.java /MP7/src/simon/mp7 line 104
Java Problem
The method compareTo(K) is undefined for the type K HeapPriorityQueue.java /MP7/src/simon/mp7 line 100
Java Problem
Bound mismatch: The type K is not a valid substitute for the bounded parameter <K extends Comparable<K>> of the type PriorityQueue<K,V> HeapPriorityQueue.java /MP7/src/simon/mp7 line 5
the message in the console is:
Exception in thread "main" java.lang.Error: Unresolved compilation problem:
Bound mismatch: The type String is not a valid substitute for the bounded parameter <V extends Comparable<K>> of the type HeapPriorityQueue<K,V>
at simon.mp7.HeapPriorityQueueDriver.main(HeapPriorityQueueDriver.java:6)
المحلول
You declare HeapPriorityQueue<K,V extends Comparable<K>>, but you try to use it as:
PriorityQueue<Integer, String> queue = new HeapPriorityQueue<Integer, String>();
But String doesn't extends Comparable<Integer> so it gives you compilation error.
