Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Just learning heaps like how to build maxHeapify, insert etc. I had a problem making a change key (increasing or decreasing the Gpa) Below in
Just learning heaps like how to build maxHeapify, insert etc. I had a problem making a change key (increasing or decreasing the Gpa)
Below in Change key method I have explained the problem
This my main Heap class
import java.util.ArrayList; import java.util.Collection; import java.util.Collections; public class MaxHeap { private ArrayListstudents; 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 child = students.size()-1; int parent = (child-1)/2; while(parent >=0 && students.get(parent).compareTo(students.get(child)) > 0) { Collections.swap(students,parent,child); } } //I HAVE GOT A PROBLEM BELOW HERE I DONT KNOW HOW TO INCREASE OR DECREASE THE KEY WITH newGPA value... I have added a int index variable, in the original we only had "s" and "newGpa" but teacher said using IndexOf is not efficient enough. public void changeKey(int index, Student s, double newGPA) { while(newGPA != students.get(index).gpa()) { if(newGPA > students.get(index).gpa()) { students.set(index,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); } } }
This one is the 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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started