所以，我真的对此感到困惑。我正在做一项家庭作业，其中涉及创建实现接口的 Heap 类和 PriorityQueue 类。其中两个接口用于 Heap 和 PriorityQueue 类，第三个是 Gradable 接口，它只有一个 toArray() 方法。
堆.java
public class Heap<T extends Comparable<? super T>> implements HeapInterface<T>,
Gradable<T> {
private T[] heapArray = (T[]) new Comparable[10];
private int heapSize = 0;
@Override
public void add(T item) {
if (item == null) {
throw new IllegalArgumentException();
} else if (size() == heapArray.length - 1){
resize();
}
heapSize++;
heapArray[heapSize] = item;
int i = heapSize;
upHeap(i);
}
@Override
public boolean isEmpty() {
return (heapSize == 0);
}
@Override
public T peek() {
return heapArray[1];
}
@Override
public T remove() {
if (size() == 0) {
return null;
} else {
T returnMin = peek();
swap(1, heapSize);
heapArray[heapSize] = null;
heapSize--;
heapify(1);
return returnMin;
}
}
@Override
public int size() {
return heapSize;
}
@Override
public T[] toArray() {
return heapArray;
}
/**
* Doubles the size of the backing array
* Big O - O(n)
*/
private void resize() {
T[] heapCopy = (T[]) new Comparable[(heapArray.length) * 2];
for (int i = 1; i < heapArray.length; i++) {
heapCopy[i] = heapArray[i];
}
heapArray = heapCopy;
}
/**
* Swaps the elements at the specified indices
* Big O - O(1)
* @param the indices to swap
*/
private void swap(int i, int j) {
T tempElement = heapArray[i];
heapArray[i] = heapArray[j];
heapArray[j] = tempElement;
}
/**
* Returns the left child index of the specified position
* Big O - O(1)
* @param index
* @return the left child index
*/
private int getLeft(int i) {
return 2 * i;
}
/**
* Returns the right child index of the specified position
* Big O - O(1)
* @param index
* @return the right child index
*/
private int getRight(int i) {
return 2 * i + 1;
}
/**
* Returns the parent index of the specified position
* Big O - O(1)
* @param index
* @return the parent index
*/
private int getParent(int i) {
return (i) / 2;
}
/**
* Readjusts the heap by going down the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void downHeap(int i) {
int left = getLeft(i);
int right = getRight(i);
while (left < heapSize) {
int pos = left;
if (heapArray[right].compareTo(heapArray[left]) < 0) {
pos = right;
}
if (heapArray[pos].compareTo(heapArray[i]) < 0) {
swap(pos, i);
left = getLeft(pos);
right = getRight(pos);
i = pos;
} else {
left = heapSize;
}
}
}
/**
* Readjusts the heap by going up the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void upHeap(int i) {
int parent = getParent(i);
while ((i > 0) && (heapArray[parent].compareTo(heapArray[i]) > 0)) {
swap(parent, i);
i = parent;
parent = getParent(i);
}
}
/**
* Readjusts the heap by going down the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void heapify(int i) {
int left = getLeft(i);
int right = getRight(i);
int pos;
if ((left < heapSize) && (heapArray[left].compareTo(heapArray[i]) < 0)) {
pos = left;
} else {
pos = i;
}
if ((right < heapSize) && (heapArray[right].compareTo(heapArray[pos]) < 0)) {
pos = right;
}
if (pos != i) {
swap(i, pos);
heapify(pos);
}
}
/**
* Readjusts the heap, beginning at height/2, by going down the heap to
* ensure heap property is maintained
* Big O - O(log(n))
*/
private void buildHeap() {
for (int i = heapSize / 2; i > 0; i--) {
heapify(i);
}
}
}
优先队列.java
public class PriorityQueue<T extends Comparable<? super T>> implements
PriorityQueueInterface<T>, Gradable<T> {
private Heap<T> priorityHeap;
@Override
public void insert(T item) {
priorityHeap.add(item);
}
@Override
public T findMin() {
return priorityHeap.peek();
}
@Override
public T deleteMin() {
return priorityHeap.remove();
}
@Override
public boolean isEmpty() {
return priorityHeap.isEmpty();
}
@Override
public void makeEmpty() {
priorityHeap = new Heap<T>();
}
@Override
public T[] toArray() {
priorityHeap.toArray();
}
}
可分级的.java
public interface Gradable<T> {
/**
* Returns the backing array of the data structure INCLUDING ANY EMPTY
* SPACES THAT MAY BE AT THE END.
* This should be a 1-line method; just return the backing array exactly as
* it is.
*
* @return the backing array of the data structure
*/
public T[] toArray();
}
堆接口.java
public interface HeapInterface<T extends Comparable<? super T>> {
/**
* Adds item to this heap
* Should throw IllegalArgumentException if item is null
* Big O - O(log(n))
* @param item the item to be added
*/
public void add(T item);
/**
* Checks if the heap is empty or not
* Big O - O(1)
* @return true if this heap is empty, false otherwise
*/
public boolean isEmpty();
/**
* Returns the minimum element of the heap without modifying the heap
* Big O - O(1)
* @return the minimum element of this heap
*/
public T peek();
/**
* Removes and returns the minimum element of this heap
* Big O - O(log(n))
* @return the minimum element of this heap
*/
public T remove();
/**
* The size of the heap
* Big O - O(1)
* @return the number of elements in this heap
*/
public int size();
}
PriorityQueueInterface.java
public interface PriorityQueueInterface<T extends Comparable<? super T>> {
/**
* Inserts an element in order in the Priority Queue
* Should throw IllegalArgumentException if item == null
* Big O - O(log(n))
* @param item the item to be inserted, it should be a data that does have
* an order property
*/
public void insert(T item);
/**
* returns the minimum value without changing the priority queue
* Should return null if queue is empty
* Big O - O(1)
* @return the minimum value without changing the priority queue
*/
public T findMin();
/**
* deletes and return the smallest item in the structure
* Big O - O(log(n))
* @return the minimum value
*/
public T deleteMin();
/**
* Checks if the queue is empty or not
* Big O - O(1)
* @return true if queue is empty, else false
*/
public boolean isEmpty();
/**
* Makes the queue empty
* Big O - O(1)
*/
public void makeEmpty();
}
但是每次编译时，我都会收到以下错误：
>javac Heap.java
Heap.java:1: error: cannot find symbol
public class Heap<T extends Comparable<? super T>> implements HeapInterface<T>,
^
symbol: class HeapInterface
Heap.java:2: error: cannot find symbol
Gradable<T> {
^
symbol: class Gradable
Heap.java:7: error: method does not override or implement a method from a supert
ype
@Override
^
Heap.java:20: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:25: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:30: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:44: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:49: error: method does not override or implement a method from a super
type
@Override
^
Note: Heap.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
8 errors
>PriorityQueue.java
PriorityQueue.java:2: error: cannot find symbol
PriorityQueueInterface<T>, Gradable<T> {
^
symbol: class PriorityQueueInterface
PriorityQueue.java:2: error: cannot find symbol
PriorityQueueInterface<T>, Gradable<T> {
^
symbol: class Gradable
PriorityQueue.java:4: error: cannot find symbol
private Heap<T> priorityHeap;
^
symbol: class Heap
location: class PriorityQueue<T>
where T is a type-variable:
T extends Comparable<? super T> declared in class PriorityQueue
PriorityQueue.java:6: error: method does not override or implement a method from
a supertype
@Override
^
PriorityQueue.java:11: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:16: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:21: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:26: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:28: error: cannot find symbol
priorityHeap = new Heap<T>();
^
symbol: class Heap
location: class PriorityQueue<T>
where T is a type-variable:
T extends Comparable<? super T> declared in class PriorityQueue
PriorityQueue.java:31: error: method does not override or implement a method fro
m a supertype
@Override
^
10 errors
我不确定是什么原因造成的，因为编译器找不到的三个接口类（HeapInterface、Gradable 和 PriorityQueueInterface）与 Heap 和 PriorityQueue 位于同一目录中。请注意，我使用 Eclipse 编写代码，然后使用 cmd 提示符编译代码。我不允许修改接口类或向 Heap 或 PriorityQueue 添加任何新的公共方法。任何帮助，将不胜感激。