ryBear - 2 months ago 12

Java Question

I have been trying to debug this code for hours. I don't know why it is not rearranging the terms. I have tried everything I can think of. Can someone help? Thanks.

`public void heapify(int i) // utility routine to percolate down from index i`

{

printHeap();

int left, r, min;

Process tmp;

left = lchild(i); // left child

r = rchild(i); // right child

if(left < size() && A[left].compareTo(A[i])<0) // find smallest child

min = left; // save index of smaller child

else

min = i;

if(r < size() && A[r].compareTo(A[min])<0)

min = r; // save index of smaller child

if(min != i) // swap and percolate, if necessary

{

tmp = A[i]; // exchange values at two indices

A[i] = A[min];

A[min] = tmp;

heapify(min);

// call heapify

}// end if

printHeap();

}// end method heapify

private int lchild(int i) {

return 2 * i + 1;

}

private int rchild(int i) {

return 2 * i + 2;

}

Even when I call heapify on every element of the heap it doesn't work :/

Here is the compareTo. It is supposed to arrange max heap using priority first then if there is a tie it goes to a unique time arrived value.

`public int compareTo(Process o) {`

int val;

if (this.priority > o.getPriority()) {

val = -1;

} else if (this.priority == o.getPriority()) {

if (this.arrivalTime < o.getArrivalTime()) { //Earlier time

val = -1;

} else {

val = 1;

}

} else {

val = 1;

}

return val;

}

Answer

The fastest known way to organize an array into a heap is called Floyd's Algorithm. You start at the middle of the array and move towards the root, sifting each item down as required. In your case:

```
for (int i = size()/2; i >= 0; --i)
{
heapify(i);
}
```

You should be able to call the `heapify`

function that you supplied.

To see how this works, take a look at http://stackoverflow.com/a/39020777/56778