Question: /* The HeapExperiment program test the MaxHeap to see the efficiency of the changeKey() method. The runtime it takes to find the index in that

/* The HeapExperiment program test the MaxHeap to see the efficiency of the changeKey() method. The runtime it takes to find the index in that method is linearithmic O(n log n). However, there is another way to find the index in O(log n) runtimes if I add another variable in the Student class and track that index in my changeKey() instead of the newGPA. I do not know how to put that into coding please help me.*/

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 = students.size()/2; i >= 0; i--) { maxHeapify(i); } } public Student getMax() { if(size() < 1) { throw new IndexOutOfBoundsException("No maximum value: the heap is empty."); } return (Student) 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); //add a new element to the array/heap int i = size()-1; //location of last index moveUp(i); //check line 161

} public void changeKey(Student s, double newGPA) { int currentIndex = 0; //find current index while(currentIndex < students.size() && s != students.get(currentIndex)) { currentIndex++; } s.setGPA(newGPA); moveUp(currentIndex); maxHeapify(currentIndex); } 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; } private 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); } }

//compare with parent node, if larger moveUp private void moveUp(int i) { //insert while(i > 0 && students.get(i).compareTo(students.get(parent(i))) > 0){ swap(i, parent(i)); i = parent(i); } } }

public class Student implements Comparable

{

private String name;

private double gpa = 0;

private int units = 0;

public Student(String name)

{

this.name = name;

}

public Student(String name, int units, double gpa)

{

this.name = name;

this.units = units;

this.gpa = gpa;

}

public String getName()

{

return name;

}

public double gpa()

{

return gpa;

}

public void setGPA(double newGPA)

{

gpa = newGPA;

}

public int units()

{

return units;

}

public void setUnits(int newUnits)

{

units = newUnits;

}

public int compareTo(Student other)

{

double difference = gpa - other.gpa;

if(difference == 0) return 0;

if(difference > 0) return 12;

return -14;

}

import java.util.ArrayList;

public class HeapExperiments

{

static int EXPERIMENT = 24;

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++) {