// right now my changeKey() method search it index n log n. How can I make this
ID: 3747405 • Letter: #
Question
// 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<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
Solution:
To find the currentIndex in your changeKey() method with logn times. Apply binary search technique to find currentIndex.
- Inbuilt binarySearch() method from Collections can be used.
- ArrayList should be sorted before calling binarySearch().
----------------------------------------------------------------------------------------------------------------------------------------
public void changeKey(Student s, double newGPA) {
Collections.sort(students); //sorting the arraylist which contain student entries/objects.
int currentIndex = Collections.binarySearch(students, s); //find current index
s.setGPA(newGPA);
moveUp(currentIndex);
maxHeapify(currentIndex);
}
So, the above binarySearch() for finding currentIndex will take logn times instead of nlogn times.
-------------------------------------------------------------------------------------------------------------------------------------
Hope it helps, Please upvote if you are happy with the answer
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.