// right now my changeKey() method search it index n log n. How can I make this more efficient, I want to search log n times. Please help.

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

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;

}

}