I am learning heaps like how to build maxHeapify, insert etc. I had a problem making a change key and addGrade function

MaxHeap associated with Student and SimpleGivenTests attached in order

description:

The given Maxheap.java includes working code to construct an empty heap, or to build a heap from a collection in linear time. It includes private helper methods, including maxHeapify. (You should understand what maxHeapify accomplishes from the videos. Don't assume you know what it accomplishes from the name. Watch and understand the first heap video.) You are also given simple working code for a Student class. For this first part of the program, nothing about Student.java should change.

You need to add code to make the public heap methods insert and changeKey work. (You might also choose to add some private methods of your own, that is allowed.) Code both of these to get them working correctly. If you follow the algorithm outlined in the second heap video, insert should naturally be efficient (logarithmic time). Your changeKey should be efficient, other than the time taken to find the student within the heap. That is okay, it is expected that your code will be inefficient for that one task. Once you find the index of the student within the heap, the rest of your changeKey should be efficient (logarithmic time).

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); for(int i = size()/2 - 1; 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 int size() { return students.size(); } public void insert(Student elt) { //Please write me. I should add the given student into the heap, //following the insert algorithm from the videos. } public void addGrade(Student elt, double gradePointsPerUnit, int units) { //Please write me. I should change the student's gpa (using a method //from the student class), and then adjust the heap as needed using //the changeKey algorithm from the videos. } 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 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); } } }

----------------------------------------------------------------------------------------------

public class Student implements Comparable { private String name; private double gradePoints = 0; private int units = 0; public Student(String name) { this.name = name; } public Student(String name, double gpa, int units) { this.name = name; this.units = units; this.gradePoints = gpa * units; } public String getName() { return name; } public double gpa() { if(units > 0) return gradePoints/units; return 0; } public void addGrade(double gradePointsPerUnit, int units) { this.units += units; this.gradePoints += gradePointsPerUnit * units; } public int compareTo(Student other) //Do not change this method. Ask me why if you like. { double difference = gpa() - other.gpa(); if(difference == 0) return 0; if(difference > 0) return 14; //Do not hardcode 14, or -12, into your code. return -12; } }

-------------------------------------------------------------------------------------------------------

import static org.junit.Assert.*; import org.junit.Test; public class SimpleGivenTests { @Test public void oneStudent() { MaxHeap heap = new MaxHeap(10); heap.insert(new Student("Susan", 3.5, 60)); assertEquals(3.5, heap.extractMax().gpa(), .000001); assertEquals(0, heap.size()); } @Test public void aInsertAFewStudents() { MaxHeap heap = new MaxHeap(10); heap.insert(new Student("Susan", 3.5, 60)); heap.insert(new Student("Ben", 3.4, 70)); heap.insert(new Student("Reed", 4.0, 120)); heap.insert(new Student("Johnny", 1.2, 50)); assertEquals(4.0, heap.extractMax().gpa(), .000001); assertEquals(3.5, heap.extractMax().gpa(), .000001); heap.insert(new Student("Billy", 2.7, 20)); assertEquals(3.4, heap.extractMax().gpa(), .000001); assertEquals(2.7, heap.extractMax().gpa(), .000001); assertEquals(1.2, heap.extractMax().gpa(), .000001); } @Test public void exceptionTest() { MaxHeap heap = new MaxHeap(10); heap.insert(new Student("Ben", 3.4, 70)); assertEquals(3.4, heap.extractMax().gpa(), .000001); try { heap.extractMax(); fail("You shouldn't reach this line, an IndexOutOfBoundsException should have been thrown."); } catch (IndexOutOfBoundsException except) { assertEquals(except.getMessage(), "No maximum value: the heap is empty."); } } @Test public void changeKeyTest() { MaxHeap heap = new MaxHeap(10); Student susan = new Student("Susan", 3, 6); Student ben = new Student("Ben", 2.4, 10); Student reed = new Student("Reed", 3.3, 3); Student johnny = new Student("Johnny", 1, 4); heap.insert(susan);; heap.insert(ben); heap.insert(johnny); heap.insert(reed); assertEquals(reed, heap.getMax()); heap.addGrade(susan, 4, 3); //should give her a 3.333333333 gpa assertEquals(susan, heap.getMax()); assertEquals(3.33333333, heap.extractMax().gpa(), .000001); heap.addGrade(reed, .7, 3); //should give him a 2.0 heap.addGrade(johnny, 4, 4); //should give him a 2.5 assertEquals(2.5, heap.extractMax().gpa(), .000001); assertEquals(2.4, heap.extractMax().gpa(), .000001); assertEquals(2.0, heap.extractMax().gpa(), .000001); } }