/* The HeapExperiment program test the MaxHeap to see the efficiency of the chan
ID: 3748867 • Letter: #
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 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<Student> students;
public MaxHeap(int capacity)
{
students = new ArrayList<Student>(capacity);
}
public MaxHeap(Collection<Student> collection)
{
students = new ArrayList<Student>(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<Student>
{
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<Student> 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<Student> 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<Student> students)
{
return new MaxHeap(students);
}
private static MaxHeap iteratedInsertionBuildHeap(ArrayList<Student> students)
{
MaxHeap heap = new MaxHeap(students.size());
for(Student s:students)
heap.insert(s);
return heap;
}
private static ArrayList<Student> createStudents(int number, boolean worstCase)
{
ArrayList<Student> students = new ArrayList<>(number);
for(int i=0; i<number; 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;
}
}
Explanation / Answer
import java.util.ArrayList;
import java.util.Collection;
public class MaxHeap
{
private ArrayList<Student> students;
public MaxHeap(int capacity)
{
students = new ArrayList<Student>(capacity);
}
public MaxHeap(Collection<Student> collection)
{
students = new ArrayList<Student>(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<Student>
{
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<Student> 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<Student> 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<Student> students)
{
return new MaxHeap(students);
}
private static MaxHeap iteratedInsertionBuildHeap(ArrayList<Student> students)
{
MaxHeap heap = new MaxHeap(students.size());
for(Student s:students)
heap.insert(s);
return heap;
}
private static ArrayList<Student> createStudents(int number, boolean worstCase)
{
ArrayList<Student> students = new ArrayList<>(number);
for(int i=0; i<number; 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;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.