Can anyone help me solve this lab? I need more explanation and comment, thanks! You have to make your own JUnit test and pass it. To make your changeKey method work efficiently, you will badly break the abstraction of the MaxHeap and Student classes, by giving each student an extra instance variable: its index within the heap. The big pay-off is that within changeKey, instead of needing linear time search to find the student within the MaxHeap, you can just ask the Student its index.

Code:

1.

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

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 - 1; 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 int size()

{

return students.size();

}

private void moveUp(int i) {

while(students.get(i).compareTo(students.get(parent(i))) > 0){

swap(i, parent(i));

i = parent(i);

}

}

public void insert(Student elt)

{

students.add(elt);

int i = students.size()-1;

moveUp(i);

}

public void addGrade(Student elt, double gradePointsPerUnit, int units){

int i = students.indexOf(elt);

students.get(i).addGrade(gradePointsPerUnit, units);

if(students.get(i).compareTo(students.get(parent(i)))>0) {

moveUp(i);

}else

maxHeapify(i);

}

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 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);

}

}

}

2.

public class Student implements Comparable

{

private String name;

private double gradePoints = 0;

private int units = 0;

public Student(String name)

{

this.name = name;

}

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

{

this.name = name;

this.units = units;

this.gradePoints = gpa * units;

}

public String getName()

{

return name;

}

public double gpa()

{

if(units > 0)

return gradePoints/units;

return 0;

}

public void addGrade(double gradePointsPerUnit, int units)

{

this.units += units;

this.gradePoints += gradePointsPerUnit * units;

}

public int compareTo(Student other) //Do not change this method. Ask me why if you like.

{

double difference = gpa() - other.gpa();

if(difference == 0) return 0;

if(difference > 0) return 14; //Do not hardcode 14, or -12, into your code.

return -12;

}

}

3.

import java.util.ArrayList; public class HeapExperiments { static int EXPERIMENT = 1; 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(); makeChanges(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 makeChanges(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 newClassGrade = Math.random() * 4; int units = (int) (1 + Math.random() * 6); heap.addGrade(s, newClassGrade, units); } } 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