2

I am working on a personal project to test heapsort on a group of objects. I am using HS to organize a set of students. using the example of a school project I already did using Selection sort I put this code together:

public static void heapify(Student[] studentList, int i, int size)
 {  

      int right = 2*i+2;
      int left = 2*i+1;
      Student leftStudent = studentList[left];
      Student rightStudent = studentList[right];
      int max;

      if(left <= size && leftStudent.getGrades() > studentList[i].getGrades())
          max = leftStudent.getGrades();          
      else            
       max = studentList[i].getGrades();


      if(right <= size && rightStudent.getGrades() > studentList[max].getGrades())
          max = rightStudent.getGrades();


      if(max != studentList[i].getGrades())
      {

         switchNodes(studentList, i, max);
         heapify(studentList, max, size);

      }

   }

I already checked to see whether I have the right helper code in other parts and I do. I keep getting an

ArrayOutofBounds Error

at the code where I call this method.

How do I successfully implement the algorithm using the Student Object calls?

PS: Helper code as follows

public static void makeHeap(Student[] studentList)
{

    for(int i = studentList.length/2; i>=0; i--)
        heapify(studentList, i, studentList.length-1);




}

public static Student[] heapSort(Student[] studentList)
{

     makeHeap(studentList);
      int sizeOfHeap = studentList.length-1;
      for(int i = sizeOfHeap; i>0; i--)       
      {

         switchNodes(studentList, 0, i);
         sizeOfHeap--;
         heapify(studentList, 0, sizeOfHeap);

      }     

    return studentList;
}

   public static void switchNodes(Student[] studentList,int i, int j)
   {

       Student temp = studentList[i];
       studentList[i] = studentList[j];
       studentList[i] = temp;

   }
2
  • What data are you calling it with? How do you know that left or right aren't greater than size-1 at the call to assign the values of leftStudent and rightStudent? Commented Nov 27, 2018 at 1:53
  • @JoeHz The code is updated reflecting the helper methods. Commented Nov 27, 2018 at 5:03

2 Answers 2

1

You didn't give the caller portion. But I found something that is risky.

int right = 2*i+2;
int left = 2*i+1;
Student leftStudent = studentList[left];
Student rightStudent = studentList[right];
int max;

if(left <= size && leftStudent.getGrades() > studentList[i].getGrades())
    max = leftStudent.getGrades();          
else            
    max = studentList[i].getGrades();


if(right <= size && rightStudent.getGrades() > studentList[max].getGrades())
    max = rightStudent.getGrades();

You checked if left and right are smaller than size, very good. But you need to do this before using these variables. When you are writing,

Student leftStudent = studentList[left];
Student rightStudent = studentList[right];

how do you know if left and right aren't accessing the memory, you haven't created yet? So my suggestion is, edit these parts to these:

int right = 2*i+2;
int left = 2*i+1;
if(left > size || right > size)
    // will you return or anything else?
    // if size if equal to list size, then you need to add >=
    // instead of only >

I'm writing again, you haven't posted the full code. But in your code, this is definitely dangerous. Change this code according to your code's logic.

Sign up to request clarification or add additional context in comments.

Comments

0

You should add this line in heapify method if(left>size || right>size) return;

Your heapify method should be something like below

public static void heapify(Student[] studentList, int i, int size)
 {  

      int right = 2*i+2;
      int left = 2*i+1;
      if(left>size || right>size) return;
      Student leftStudent = studentList[left];
      Student rightStudent = studentList[right];
      int max;

      if(left <= size && leftStudent.getGrades() > studentList[i].getGrades())
          max = leftStudent.getGrades();          
      else            
       max = studentList[i].getGrades();


      if(right <= size && rightStudent.getGrades() > studentList[max].getGrades())
          max = rightStudent.getGrades();


      if(max != studentList[i].getGrades())
      {

         switchNodes(studentList, i, max);
         heapify(studentList, max, size);

      }

   }

Complete working code

class Student
{
    int id;
    int grade;
    public int getGrades()
    {
        return grade;
    }
    public Student(int id,int grade)
    {
        this.id=id;
        this.grade=grade;
    }
}
public class HelloWorld{

     public static void heapify(Student[] studentList, int i, int size)
 {  

      int right = 2*i+2;
      int left = 2*i+1;
      if(left>size || right>size) return;
      Student leftStudent = studentList[left];
      Student rightStudent = studentList[right];
      int max;

      if(left <= size && leftStudent.getGrades() > studentList[i].getGrades())
          max = leftStudent.getGrades();          
      else            
       max = studentList[i].getGrades();


      if(right <= size && rightStudent.getGrades() > studentList[max].getGrades())
          max = rightStudent.getGrades();


      if(max != studentList[i].getGrades())
      {

         switchNodes(studentList, i, max);
         heapify(studentList, max, size);

      }

   }

public static void makeHeap(Student[] studentList)
{

    for(int i = studentList.length/2; i>=0; i--)
        heapify(studentList, i, studentList.length-1);




}

public static Student[] heapSort(Student[] studentList)
{

     makeHeap(studentList);
      int sizeOfHeap = studentList.length-1;
      for(int i = sizeOfHeap; i>0; i--)       
      {

         switchNodes(studentList, 0, i);
         sizeOfHeap--;
         heapify(studentList, 0, sizeOfHeap);

      }     

    return studentList;
}

   public static void switchNodes(Student[] studentList,int i, int j)
   {

       Student temp = studentList[i];
       studentList[i] = studentList[j];
       studentList[i] = temp;

   }
  public static void main(String[] args)
  {
      Student[] students= new Student[10];
      for(int i=0;i<10;i++)
      {
       students[i]=new Student(i,i);   
      }
      makeHeap(students);
  }
}

2 Comments

the studentList[max].getGrades()) part is what seems to be giving me the problem.
if you don't have if(left>size || right>size) return; this statement , StudentList [left] will give problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.