I have a homework that the teacher test if it's corrects by checking it's output using this website moodle.caseine.org, so to test my code the program execute these lines and compare the output with the expected one, this is the test :
Tas t = new Tas();
Random r = new Random(123);
for(int i =0; i<10000;i++)t.inser(r.nextInt());
for(int i =0;i<10000;i++)System.out.println(t.supprMax());
System.out.println(t);
And my Heap (Tas) class:
package td1;
import java.util.ArrayList;
import java.util.List;
public class Tas {
private List<Integer> t;
public Tas() {
t = new ArrayList<>();
}
public Tas(ArrayList<Integer> tab) {
t = new ArrayList<Integer>(tab);
}
public static int getFilsGauche(int i) {
return 2 * i + 1;
}
public static int getFilsDroit(int i) {
return 2 * i + 2;
}
public static int getParent(int i) {
return (i - 1) / 2;
}
public boolean estVide() {
return t.isEmpty();
}
@Override
public String toString() {
String str = "";
int size = t.size();
if (size > 0) {
str += "[" + t.get(0);
str += toString(0);
str += "]";
}
return str;
}
public boolean testTas() {
int size = t.size();
int check = 0;
if (size > 0) {
for (int i = 0; i < t.size(); i++) {
if (getFilsGauche(i) < size) {
if (t.get(i) < t.get(getFilsGauche(i))) {
check++;
}
}
if (getFilsDroit(i) < size) {
if (t.get(i) < t.get(getFilsDroit(i))) {
check++;
}
}
}
}
return check == 0;
}
public String toString(int i) {
String str = "";
int size = t.size();
if (getFilsGauche(i) < size) {
str += "[";
str += t.get(getFilsGauche(i));
str += toString(getFilsGauche(i));
str += "]";
}
if (getFilsDroit(i) < size) {
str += "[";
str += t.get(getFilsDroit(i));
str += toString(getFilsDroit(i));
str += "]";
}
return str;
}
//insert value and sort
public void inser(int value) {
t.add(value);
int index = t.size() - 1;
if (index > 0) {
inserCheck(index); // O(log n)
}
}
public void inserCheck(int i) {
int temp = 0;
int parent = getParent(i);
if (parent >= 0 && t.get(i) > t.get(parent)) {
temp = t.get(parent);
t.set(parent, t.get(i));
t.set(i, temp);
inserCheck(parent);
}
}
//switch position of last element is list with first (deletes first and return it)
public int supprMax() {
int size = t.size();
int max = 0;
if (size > 0) {
max = t.get(0);
t.set(0, t.get(size - 1));
t.remove(size - 1);
supprMax(0);
}
else {
throw new IllegalStateException();
}
return max;
}
public void supprMax(int i) {
int size = t.size();
int temp = 0;
int index = i;
if (getFilsGauche(i) < size && t.get(getFilsGauche(i)) > t.get(index)) {
index = getFilsGauche(i);
}
if (getFilsDroit(i) < size && t.get(getFilsDroit(i)) > t.get(index)) {
index = getFilsDroit(i);
}
if (index != i) {
temp = t.get(index);
t.set(index, t.get(i));
t.set(i, temp);
supprMax(index);
}
}
public static void tri(int[] tab) {
Tas tas = new Tas();
for (int i = 0; i < tab.length; i++) {
tas.inser(tab[i]);
}
for (int i = 0; i < tab.length; i++) {
tab[i] = tas.supprMax();
}
}
}
The last 3 lines of the test are :
-2145024521 -2147061786 -2145666206
But the last 3 of my code are :
-2145024521 -2145666206 -2147061786
The problem are probably with the inser and supprMax methods.
I hate to get a bad grade just because of 3 lines placement, because it is a program that verify the code, it dosn't care the the solution was close, it's still says it's wrong.