How do I find a different way to get the index of the student with less time than linear time in indexOf()? Right now I am thinking of giving each student an extra field that stores their index and then instead of having to find the student in the heap I can just ask it where it is but I do not know how to implement that. I would definitely appreciate help. Thanks.

Here is my MaxHeap Class:

import java.util.ArrayList;

import java.util.Collection;

import java.util.List;

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

}

}

}

Here is my student class:

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