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
} 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++) {
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
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
{
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
{
return new MaxHeap(students);
}
private static MaxHeap iteratedInsertionBuildHeap(ArrayList
{
MaxHeap heap = new MaxHeap(students.size());
for(Student s:students)
heap.insert(s);
return heap;
}
private static ArrayList
{
ArrayList
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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started