只是通过堆来遇到一些问题。我根据我正在使用的接口限制了界限，并且我正在尝试访问一个有效添加堆的构造函数，以证明与通过插入添加堆相比，时间复杂度降低了。换句话说，我需要这个构造函数才能工作，但驱动程序不允许我将 MaxHeapInterface 对象初始化为整数。有什么想法吗？
import java.util.Arrays;
public final class MaxHeap<T extends Comparable<? super T>> implements
MaxHeapInterface<T>
{
private T[] heap;
private int backIndex;
private static final int DEFAULT_CAP = 101;
private static final int MAX_CAP = 101;
private int efficientCounter=0;
private int counter=0;
public MaxHeap()
{
this(DEFAULT_CAP);
}
public MaxHeap(int chosenCap)
{
if(chosenCap < DEFAULT_CAP )
chosenCap = DEFAULT_CAP;
else
checkCapacity(chosenCap);
@SuppressWarnings("unchecked")
T[] holdHeap = (T[]) new Comparable[chosenCap +1];
heap = holdHeap;
backIndex = 0;
}
//efficient addition method-constructor
public MaxHeap(T[] entry)
{
this(entry.length);
for(int i =0; i < entry.length; i++)
heap[i+1] = entry[i];
for(int j = backIndex/2; j > 0; j-- )
{
reHeap(j);
}
}
//other addition method
public void add(T entry)
{
int index = backIndex+1;
int halfIndex = index/2;
counter++;
while((halfIndex > 0) && entry.compareTo(heap[halfIndex])>0)
{
heap[index] = heap[halfIndex];
index = halfIndex;
halfIndex = index/2;
counter++;
}
heap[index] = entry;
backIndex++;
}
public T removeMax()
{
T root = null;
if(!isEmpty())
{
root = heap[1];
heap[1] = heap[backIndex];
backIndex--;
reHeap(1);
}
return root;
}
public T getMax()
{
T root = null;
if(!isEmpty())
root = heap[1];
return root;
}
public boolean isEmpty()
{
return backIndex < 1;
}
public int getSize()
{
return backIndex;
}
public void clear()
{
while(backIndex > -1)
{
heap[backIndex] = null;
backIndex--;
}
backIndex = 0;
}
public int getEffcientcounter()
{
return efficientCounter;
}
public int getCounter()
{
return counter;
}
private void reHeap(int index)
{
boolean done = false;
T alone = heap[index];
int leftChildLocation = 2*index;
while(!done && (leftChildLocation <= backIndex))
{
int biggerChildLocation = leftChildLocation;
int rightChildLocation = leftChildLocation +1;
if((rightChildLocation <= backIndex)&& heap[rightChildLocation].compareTo(heap[biggerChildLocation])>0)
{
biggerChildLocation = rightChildLocation;
}
if(alone.compareTo(heap[biggerChildLocation])<0)
{
heap[index] = heap[biggerChildLocation];
index = biggerChildLocation;
leftChildLocation = index *2;
}
else{
done = true;
}
heap[index] = alone;
}
}
private void checkCapacity(int size)
{
if(size>MAX_CAP)
throw new IllegalStateException("Attempt to create a bag way too big." +
"\n the limit is "+ MAX_CAP);
}
public void printHeap()
{
for(int i = 0; i < heap.length; i++)
System.out.print(heap[i]+"," +" ");
}
}
这是我的驱动程序，不幸的是未完成
import java.util.*;
public class Driver
{
public static void main(String args[])
{
boolean integerChecker = true;
String input;
int choice;
Scanner kb = new Scanner(System.in);
MaxHeapInterface<Integer> randomHeap = new MaxHeap<>(101);
MaxHeapInterface<Integer> sequentialHeap = new MaxHeap<>(101);
ArrayList<Integer> list = new ArrayList<Integer>();
int[] array = new int[101];
int[] array2 = new int[101];
System.out.println("Please select how to test the program:");
System.out.println("(1) 20 sets of 100 randomly generated integers");
System.out.println("(2) Fixed Integer Values 1-100");
System.out.print("Enter Choice: ");
input = kb.next();
kb.nextLine();
integerChecker = isInteger(input);
choice = Integer.parseInt(input);
while(!integerChecker || choice<0 || choice >2)
{
System.out.println("Please input a valid choice: ");
input = kb.next();
kb.nextLine();
integerChecker = isInteger(input);
choice = Integer.parseInt(input);
}
for(int i = 1; i <= 100; i++)
list.add(i);
if(choice == 1 )
{
Collections.shuffle(list);
for(int i =1; i <100; i++)
{
randomHeap.add(list.get(i));
array[i]= list.get(i);
}
//ERROR HERE
MaxHeapInterface<Integer> betterRandomHeap = new MaxHeap<>(array);
System.out.println("Average swaps for series of insertions");
System.out.println("Average swaps for optimal method: ");
}
if (choice == 2)
{
for(int i = 1; i < list.size(); i++)
{
sequentialHeap.add(i);
array2[i]= list.get(i);
}
//ERROR HERE
MaxHeapInterface<Integer> betterSequentialHeap= new MaxHeap<>
(array2);
System.out.println("Heap built using series of insertions: ");
sequentialHeap.printHeap();
System.out.println("Number of swaps: ");
System.out.println("Heap after 10 removals: ");
System.out.println();
System.out.println("Heap built using optimal method: ");
betterSequentialHeap.printHeap();
System.out.println("Number of swaps: ");
System.out.println("Heap after 10 removals: ");
}
}
private static boolean isInteger(String str)
{
if (str == null) {
return false;
}
if (str.isEmpty()) {
return false;
}
int i = 0;
if (str.charAt(0) == '-')
{
if (str.length() == 1) {
return false;
}
i = 1;
}
for (i =0; i < str.length(); i++)
{
char c = str.charAt(i);
if (c < '0' || c > '9') {
return false;
}
}
return true;
}
}
这是我的界面
public interface MaxHeapInterface<T extends Comparable<? super T>>
{
public void add(T entry);
public T removeMax();
public T getMax();
public boolean isEmpty();
public int getSize();
public void clear();
public void printHeap();
}