/* I want to track my indexes for the students class to make my algorithm more efficient. I was able to set the indexes and get them, but how do I test where my indexes are located? please help/explain how do I test those indexes in my test program. Thanks*/

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); //set index for each students for(int i = 0; i < collection.size();i++) { students.get(i).setIndex(i); } 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 = students.size()-1; //replace students.size()-1 elt.setIndex(i); //set index for the element moveUp(i); //moveUp if index is larger } public void changeKey(Student s, double newGPA) { int index = s.getIndex(); //get the current index s.setGPA(newGPA); if(students.get(parent(index)).compareTo(students.get(index)) > 0) { moveUp(index); } else { maxHeapify(index); } } 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.get(from).setIndex(to); students.get(to).setIndex(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) { 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;

private int index = 0;

public Student(String name) {

this.name = name;

}

public Student(int index, String name, int units, double gpa) {

this.name = name;

this.units = units;

this.gpa = gpa;

this.index = index;

}

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 index() {

return index;

}

public int getIndex() {

return index;

}

public void setIndex(int newIndex) {

index = newIndex;

}

public int compareTo(Student other)

{

double difference = gpa - other.gpa;

if(difference == 0) return 0;

if(difference > 0) return 12;

return -14;

}

}

import static org.junit.Assert.*;

import org.junit.Before; import org.junit.Test;

public class MaxHeapTest { private MaxHeap heap;

@Before public void setUp() throws Exception { heap = new MaxHeap(10); Student Annie = new Student(, "Annie", 0, 0.0); Student Brandon = new Student(0, "Brandon", 120, 3.6); Student Cathy = new Student("Cathy", 110, 2.3); Student Dana = new Student("Dana", 40, 3.3); Student Emily = new Student("Emily"); Student Foxy = new Student("Foxy", 70, 3.0); heap.insert(Annie); heap.insert(Brandon); heap.insert(Cathy); heap.insert(Dana); heap.insert(Emily); heap.insert(Foxy);

heap.changeKey(Foxy, 3.4); heap.changeKey(Cathy, 4.0); heap.changeKey(Dana, 3.3); Emily.setUnits(115); Emily.setGPA(3.8); }

@Test public void test() throws Exception { assertEquals(3.6, heap.extractMax().gpa(), 0.00001); assertEquals(4.0, heap.extractMax().gpa(), 0.00001); assertEquals("Emily", heap.extractMax().getName()); assertEquals(70, heap.extractMax().units(), 0.00001); } }