rendered paste bodypublic void insert(E item) {
int k = size;
heapArray[k] = item;
int i = (k - 1) / 3;
//System.out.println( "item: "+ heapArray[i] + ", childloc: " + k + ", child: " + heapArray[k] + " parent " + heapArray[i] + ", parentloc " + i );
//System.out.println( "heapArray[k].compareTo( heapArray[i] ) ) "+ ( ( heapArray[k].compareTo( heapArray[i] ) ) < 0 ) );
while( ( heapArray[k].compareTo( heapArray[i] ) ) < 0 ) {
//parent shifted down
heapArray[k] = heapArray[i];
//child shifted up
heapArray[i] = item;
//remake child at parent
k = i;
//find new parent
i = (k - 1) / 3;
}
size++;
}
/*
*
*
*
*/
public E remove() throws UnderflowException {
// k is location of parent
int k = 0;
//i is location of child
int i = 0;
E retItem = heapArray[k];
size--;
heapArray[k] = heapArray[size];
i = 3*k + 1;
if ( heapArray[ i ].compareTo( heapArray[ 3*k + 2 ] ) > 0 ) {
i = 3*k + 2;
}
if ( heapArray[ i ].compareTo( heapArray[ 3*k + 3 ] ) > 0 ) {
i = 3*k + 3;
}
while( ( (heapArray[k].compareTo( heapArray[i] ) ) > 0 )&&(heapArray[k] != null)&&(heapArray[i]!= null) ){
//parent = child;
E item = heapArray[k];
heapArray[k] = heapArray[i];
//child = parent
heapArray[i] = item;
if( i <=size ) {
k = i;
i = 3*k + 1;
}
if( i <=size ) {
if ( heapArray[ i ].compareTo( heapArray[ 3*k + 2 ] ) > 0 ) {
i = 3*k + 2;
}
}
if( i <=size ) {
if ( heapArray[ i ].compareTo( heapArray[ 3*k + 3 ] ) > 0 ) {
i = 3*k + 3;
}
}
heapArray[i] = item;
}
return retItem;