How do I find a different way to get the index of the student with less time tha
ID: 3748745 • Letter: H
Question
How do I find a different way to get the index of the student with less time than linear time in indexOf()? Pretty much make changeKey to O(log n) complexity.
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
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 = size()/2; 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 void insert(Student elt)
{
students.add(elt);
int i = students.size()-1;
bubbleUp(i);
}
public void bubbleUp(int i)
{
while(i>0 && students.get(i).compareTo(students.get(parent(i))) > 0)
{
swap(i,parent(i));
//moves up to the next level
i=parent(i);
}
}
public void changeKey(Student s, double newGPA)
{
s.setGPA(newGPA);
int i = students.size()-1;
maxHeapify(students.indexOf(s));
bubbleUp(students.indexOf(s));
}
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);
}
}
}
Explanation / Answer
You can instead of using the indexOf() method, use your own searching method based on Binary Search. This will give you a complexity of O(log n) which is faster than O(n). Here, is a small example of how I would have written it:
**************************************CODE*********************************************************************************
import java.util.*;
class Student implements Comparable<Student>
{
int id ;
Student(int id)
{
this.id = id;
}
public int compareTo(Student s)
{
if(this.id==s.id)
return 0;
else if(this.id>s.id)
return 1;
else
return -1;
}
}
public class Main
{
// Returns index of s if it is present in array students[l-r], else return -1
static int findIndexOf(Student students[], Student s, int l_index, int r_index)
{
if (r_index>=l_index)
{
int mid = l_index + (r_index - l_index)/2;
// If the s is present at the middle index
if (students[mid].compareTo(s) == 0)
return mid;
// If s is smaller than element at mid index, then s should be present in left subarray
if (students[mid].compareTo(s) == 1)
return findIndexOf(students, s, l_index, mid-1);
// Else the s should be present in right subarray
return findIndexOf(students, s, mid+1, r_index);
}
// If element is not present in array
return -1;
}
public static void main(String args[])
{
Student s1 = new Student(1);
Student s2 = new Student(2);
Student s3 = new Student(3);
Student s4 = new Student(4);
Student students[] = {s1, s2, s3, s4};
int n = students.length;
Student x = new Student(1);
int result = findIndexOf(students,x,0,n-1);
if (result == -1)
System.out.println("Element not present.");
else
System.out.println("Element found at index : " + result);
}
}
**************************************************************************************************************************
Since, class Student wasn't provided, I used an array of Student type objects. I am guessing you are already handling the comparison operator for Student objects to check whether two objects are equal or not. If not you can use my dummy Student class to make necessary changes and you can use this method as a reference to create a new one with slight modifications. This method runs with time complexity O(log n) which is your main objective.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.