对于类(class),我必须实现 BST 或 heapSort。我做了 BST,但认为也知道这一点会很好,但现在我被困住了。这是我第一次使用堆(并且真正使用泛型编码/实现 Comparable,所以我为所有错误道歉)并且我遇到了实现 compareTo 的问题。
本质上,我希望能够将通用对象添加到我的堆数组中,然后比较它们以进行堆排序。我使用 compareTo 在添加到堆时检查新条目并在 reheap 方法中进行交换。
我返回的错误:
Heap.java:64: error: bad operand types for binary operator '<'
if (this < other)
^
first type: Heap<T>
second type: Heap<T>
where T is a type-variable:
T extends Comparable<T> declared in class Heap
虽然我不确定如何解决这个问题。我知道我的二元运算符不适用于泛型,但我不知道如何解决它。 感谢您的任何输入。对于您可能发现的所有初学者错误,我们深表歉意! 这是我的代码:
import java.util.*;
class Heap<T extends Comparable <T>> implements Comparable<Heap<T>>{
private T[] heap;
private int lastIndex;
private static final int CAPACITY = 25;
public Heap(){
this(CAPACITY);
}
public Heap(int capacity){
heap = (T[])new Comparable[capacity+1];
lastIndex = 0;
}
public void add(T newEntry){
lastIndex++;
if(lastIndex>=heap.length)
doubleArray();
int newIndex = lastIndex;
int parentIndex = newIndex/2;
while((parentIndex>0)&&(heap[parentIndex].compareTo(newEntry)>0))
{
heap[newIndex] = heap[parentIndex];
newIndex = parentIndex;
parentIndex = newIndex/2;
}
heap[newIndex] = newEntry;
}
public void display()
{
for(int i=1;i<heap.length;i++)
{
System.out.println(heap[i]);
}
}
private void doubleArray()
{
T[] oldHeap = heap;
int oldSize = heap.length;
heap = (T[]) new Object[2*oldSize];
for(int i =0; i < oldSize-1;i++)
{
heap[i] = oldHeap[i];
}
}
public int compareTo(Heap<T> other)
{
int sort = 0;
if (this < other)
{
sort = -1;
}
else if (this> other)
{
sort = 1;
}
else
{
sort = 0;
}
return sort;
}
private <T extends Comparable<T>> void reheap(T[] heap, int rootIndex, int lastIndex)
{
boolean done=false;
T orphan = heap[rootIndex];
int leftChildIndex = 2 * rootIndex + 1;
while(!done && (leftChildIndex<=lastIndex))
{
int largerChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if(rightChildIndex<=lastIndex && (heap[rightChildIndex].compareTo(heap[largerChildIndex])>0))
largerChildIndex = rightChildIndex;
if(orphan.compareTo(heap[largerChildIndex])<0)
{
// System.out.println(orphan+ "--" + largerChildIndex);
heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex+1;
}
else
done = true;
}
heap[rootIndex] = orphan;
}
public <T extends Comparable<T>> void heapSort(int n)
{
for(int rootIndex = n/2-1;rootIndex >=0;rootIndex--)
reheap(heap,rootIndex,n-1);
swap(heap,0,n-1);
for(int lastIndex = n-2;lastIndex > 0;lastIndex--)
{
reheap(heap,0,lastIndex);
swap(heap,0,lastIndex);
}
}
private <T extends Comparable<T>> void swap(T[] a,int first, int last)
{
T temp;
temp = a[first];
a[first] = a[last];
a[last] = temp;
}
}
非常感谢任何帮助
最佳答案
您不希望您的堆是
Comparable
;你想比较它的成员。因此删除implements Comparable<Heap<T>>
从你的类声明中删除compareTo
方法。您的许多方法(
reheap
、heapSort
、swap
)冗余地声明了<T extends Comparable<T>>
您已经在用T
参数化的类的上下文中.删除那些声明。
关于java - compareTo 与 heapSort 的泛型,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20345999/