/* I want to track my indexes for the students class to make my algorithm more e
ID: 3749224 • Letter: #
Question
/* 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<Student> students;
public MaxHeap(int capacity) {
students = new ArrayList<Student>(capacity);
}
public MaxHeap(Collection<Student> collection) {
students = new ArrayList<Student>(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<Student> {
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);
}
}
Explanation / Answer
To validate those indexes, you need to set it accordingly. You have to determine which one you want to use as index. Either unit or gpa.
Modified Test class:
It will pass only 3 params to student class.
import static org.junit.Assert.assertEquals;
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( "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", 123, 2.1);
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);
}
}
Student class Modified:
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
public class Student implements Comparable<Student> {
private String name;
private double gpa = 0;
private int units = 0;
private int index = 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;
this.index = units;//If you want to form your max heap based on units
//this.index = (int) Math.round(gpa); //Use this if you want to use gpa as your heapifying property
}
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;
}
}
Here constructror is modified. Added two lines. One is for unit as index. Another one is for gpa as index. Since index is integer, rounded value of gpa can be used.
In case of any doubts, please comment.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.