Write the code breaking abstraction to have better efficiency for insert method and changeKey. There is also HeapExperiments file to test efficiency

Hint: Make your changeKey method to O(lg n). You may use indexOf(object) to get the student index in the arrayList, which will cause your method is O(nlg n). Thus, eliminate it!

import java.util.ArrayList; import java.util.Collection;

public class MaxHeap { private ArrayList students; public MaxHeap(int capacity) { students = new ArrayList(capacity); } public MaxHeap(Collection collection) { students = new ArrayList(collection); for(int i = size()/2; i >= 0; i--) { maxHeapify(i); } } public Student getMax() { if(size() < 1) { throw new IndexOutOfBoundsException("No maximum value: the heap is empty."); } return students.get(0); } public Student extractMax() { Student value = getMax(); students.set(0,students.get(size()-1)); students.remove(size()-1); maxHeapify(0); return value; } public void insert(Student elt) { students.add(elt); //adding a student to the last position of the array int i = students.size()-1; //starting from the end of the array moveUp(i); } public void changeKey(Student s, double newGPA) { //Please write me. { int current = 0; while(current < students.size() && s != students.get(current)) //look for the position of the key we want to change. { current++; } s.setGPA(newGPA); //it either goes up or down or stays in the same position in the array moveUp(current); maxHeapify(current); }

}

private int parent(int index) { return (index - 1)/2; } private int left(int index) { return 2 * index + 1; } private int right(int index) { return 2 * index + 2; } int size() { return students.size(); } private void swap(int from, int to) { Student val = students.get(from); students.set(from, students.get(to)); students.set(to, val); } private void maxHeapify(int index) { int left = left(index); int right = right(index); int largest = index; if (left < size() && students.get(left).compareTo(students.get(largest)) > 0) { largest = left; } if (right < size() && students.get(right).compareTo(students.get(largest)) > 0) { largest = right; } if (largest != index) { swap(index, largest); maxHeapify(largest); } } private void moveUp(int i) { while (i > 0 && students.get(i).compareTo(students.get(parent(i))) > 0) { swap(i,parent(i)); i = parent(i); } }

}

import java.util.ArrayList;

public class HeapExperiments

{

static int EXPERIMENT = 4;

static int CHANGES = 1000;

public static void main(String[] args)

{

System.out.println("Experiment number " + EXPERIMENT);

switch(EXPERIMENT) {

case 1:

experiments(10000, false, false, false);

break;

case 2:

experiments(100000, false, false, false);

break;

case 3:

experiments(1000000, false, false, false);

break;

case 4:

experiments(10000, false, false, false);

experiments(10000, true, false, false);

break;

case 5:

experiments(100000, false, false, false);

experiments(100000, true, false, false);

break;

case 6:

experiments(1000000, false, false, false);

experiments(1000000, true, false, false);

break;

case 7:

experiments(10000, true, false, false);

experiments(10000, false, false, false);

break;

case 8:

experiments(100000, true, false, false);

experiments(100000, false, false, false);

break;

case 9:

experiments(1000000, true, false, false);

experiments(1000000, false, false, false);

break;

case 10:

experiments(10000, true, false, false);

break;

case 11:

experiments(100000, true, false, false);

break;

case 12:

experiments(1000000, true, false, false);

break;

case 13:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(10000, false, false, false);

}

break;

case 14:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(10000, true, false, false);

}

break;

case 15:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(100000, false, false, false);

}

break;

case 16:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(100000, true, false, false);

}

break;

case 17:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(1000000, false, false, false);

}

break;

case 18:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(1000000, true, false, false);

}

break;

case 19:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(10000, true, true, false);

}

break;

case 20:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(100000, true, true, false);

}

break;

case 21:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(1000000, true, true, false);

}

break;

case 22:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(10000, false, false, true);

}

break;

case 23:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(100000, false, false, true);

}

break;

case 24:

for(int i=0; i<10; i++) {

System.out.println("Run " + (i+1) + " of 10");

experiments(1000000, false, false, true);

}

break;

default:

break;

}

}

public static void experiments(int population, boolean iteratedInsertion, boolean worstCase, boolean changeKey) {

MaxHeap heap;

long startTime, endTime, duration;

ArrayList students;

System.out.println("Building a heap of " + population + " students:");

if(!iteratedInsertion)

{

students = createStudents(population, worstCase);

startTime = System.nanoTime();

heap = linearBuildHeap(students);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("Linear-time build time = " + duration);

} else {

students = createStudents(population, worstCase);

startTime = System.nanoTime();

heap = iteratedInsertionBuildHeap(students);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("Iterated-insertion build time = " + duration);

if(worstCase)

System.out.println("Worst case input used!!!");

}

System.out.println("Time per student = " + duration/population + " ");

if(changeKey)

{

startTime = System.nanoTime();

makeErrors(students, heap, population);

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("Time to make " + CHANGES + " changes = " + duration);

System.out.println("Time per change = " + duration/CHANGES + " ");

}

}

private static void makeErrors(ArrayList students, MaxHeap heap, int size)

{

for(int i = 0; i < CHANGES; i++)

{

int index = (int) (Math.random() * size);

Student s = students.get(index);

double newGPA = Math.random() * 8;

heap.changeKey(s, newGPA);

}

}

private static MaxHeap linearBuildHeap(ArrayList students)

{

return new MaxHeap(students);

}

private static MaxHeap iteratedInsertionBuildHeap(ArrayList students)

{

MaxHeap heap = new MaxHeap(students.size());

for(Student s:students)

heap.insert(s);

return heap;

}

private static ArrayList createStudents(int number, boolean worstCase)

{

ArrayList students = new ArrayList<>(number);

for(int i=0; i

{

int units = (int) (Math.random() * 100);

double gradePoints;

if(worstCase)

gradePoints = 4.0 * i / number;

else

gradePoints = Math.random() * 4; //Random gradePoints

students.add(new Student("student" + i, units, gradePoints));

}

return students;

}

}