0

我有一个家庭作业问题如下:

创建了将实现优先级队列的 HeapPriorityQueue

import 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;  
    }  

}  

这应该实现这个 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;  
}  

而Driver类是这个

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  
}  

我遇到的问题是

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) 
4

1 回答 1

1

您声明HeapPriorityQueue<K,V extends Comparable<K>>,但您尝试将其用作:

PriorityQueue<Integer, String> queue = new HeapPriorityQueue<Integer, String>();

String事实并非extends Comparable<Integer>如此,它会给您带来编译错误。

于 2013-09-08T12:44:45.547 回答