I know this is an amaetuer error, i understand what it means but i dont understand why i cant fix it. Ive been trying everything. Im trying to take an array of type T and switch its values around so it correctly corresponds to the rules of a heap, where the parent is always greater than the 2 children. The error is in my while loop
please dont be harsh if its something easily fixable. ive been struggling heavily and cant seem to find an answer.
public class myheap<T extends Comparable<T>> extends heap<T>
{
// constructors of the subclass should be written this way:
public myheap(int max) { super(max); }
public myheap(T[] A) {super(A);}
public void buildheap(T[] Arr){
int size = Arr.length;
int startsize = (size-1)/2;
for(int i=startsize;i>0;i--){
int l = left(i);
int r = right(i);
T temp = null;
while((Arr[r]!=null) && Arr[i].compareTo(Arr[r])<0){
if (Arr[l].compareTo(Arr[r])>0){
temp = Arr[l];
Arr[l] = Arr[i];
Arr[i] = temp;
}//if left is greater than right
else //then right must be greater than parent
temp = Arr[r];
Arr[r] = Arr[i];
Arr[i] = temp;
}//whileloop
if((Arr[r]==null) && Arr[i].compareTo(Arr[l])<0)
temp = Arr[l];
Arr[l] = Arr[i];
Arr[i] = temp;
}//for
}//buildheap
public static void main(String[] args){
String[] array = {"SH","AH","AB","YA","AY","AA","AB","LM","LL","LO"};
myheap<String> New = new myheap<String>(array.length);
for(int i=0;i<array.length;i++){
New.insert(array[i]);
}//insert
New.buildheap(array);
New.drawheap();
for(int i=0;i<array.length;i++){
System.out.println(New.deletemax() + " ");
}//for
System.out.println();
} //main
}
Heap superclass that myheap is extending
/*
Polymorphic priority heaps, largest value on top.
Heap axiom. The value at every node cannot be smaller than the values
at each of its children nodes.
Use internal array to implement heap "tree", with index 0 representing
the root. Given node index i, left(i)= 2*i+1 and right(i)=2*i+2, while
parent(i) = (i-1)/2.
*/
class heap<T extends Comparable<T>>
{
protected T[] H; // internal array representing heap.
protected int size; // size of current heap, not same as H.length!
public int size() { return size; } // size is read-only externally.
public int maxsize() { return H.length; }
public heap(T[] A) { H = A; size=0; } // preferred constructor
public heap(int m) // will cause compiler warning (ok to ignore)
{
H = (T[]) new Comparable[m]; // downcast from Object is OK.
size = 0;
}
protected int left(int i) { return 2*i+1; }
protected int right(int i) { return 2*i+2; }
protected int parent(int i) { return (i-1)/2; }
// protected is important!
// lookup heap, without delete
public T getmax()
{
if (size<1) return null;
return H[0];
}
// insert x into heap: place at end, then propagate upwards
// returns false on failure.
public boolean insert(T x)
{
if (size > H.length-1) return false;
H[size++] = x; // place at end, inc size
// propagate upwards
int cur = size-1; // current position
int p = parent(cur);
while (cur>0 && H[cur].compareTo(H[p])>0)
{ // propagate upwards
T temp = H[cur];
H[cur] = H[p]; H[p] = temp;
cur = p; // switch current to parent
p = parent(cur); // recalc parent
}//while
return true;
}//insert
// deletetop: take last element, move to top, propagate downwards:
public T deletemax()
{
if (size<0) return null;
T answer = H[0];
H[0] = H[--size]; // place at top:
// now propagate downwards.
boolean done = false;
int i = 0; // current position
int c = 0; // swap candidate
while (c != -1)
{
int l = left(i);
int r = right(i);
c = -1; // swap candidate
if (l<size && H[l].compareTo(H[i])>0) c = l; // set candidate to left
if (r<size && H[r].compareTo(H[i])>0 && H[r].compareTo(H[l])>0) c=r;
if (c!= -1)
{
T temp = H[i]; H[i] = H[c]; H[c] = temp;
i = c;
}
}//while
return answer;
}//deletemax
// but search is not log(n). Why?
public boolean search(T x)
{
for(int i=0;i<size;i++) {if (x.compareTo(H[i])==0) return true;}
return false;
}
public void drawheap() // use only with heapdisplay.java program
{
heapdisplay W = new heapdisplay(1024,768);
W.drawtree(H,size);
}
}//heap
public class heaps14
{
/**public static void main(String[] args){
heap<Integer> HI = new heap<Integer>(200);
for(int i=0;i<100;i++) HI.insert((int)(Math.random()*1000));
HI.drawheap();
for(int i=0;i<100;i++) System.out.print(HI.deletemax() + " ");
System.out.println();
}//main**/
}
