Incorrect implementation of Heap Sort

Question

This is a modified implementation of Heap Sort taken from a website.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HeapSort 
{
    static  int heapsize;

    public static void main(String args[])
    {
        Vector<Integer> container = new Vector<Integer>(); // container used to store txt file integers
        Scanner myScanner = new Scanner("foo"); // variable used to read file
        String userinput="data1.txt";


        try
        {
            //open filename
            //got problem , must think how to do relative path instead of absolute path
             File inputfile = new File("C:\\Users\\8382c\\workspace\\AdvanceAlgorithmA3_Heapsort\\src\\" + userinput);
             myScanner = new Scanner(inputfile);

        }
        catch(FileNotFoundException e)
        {
            System.out.println("File cant be found");
        }



        String line = myScanner.nextLine(); //read 1st line which contains the number of numbers to be sorted

        while (myScanner.hasNext())
        {
            container.add(myScanner.nextInt());
        }



        heapsize = container.size();

        System.out.println(heapsize);

        sort(container);

        int x =10;

        /*for (int i=0 ; i < container.size() ; i ++)
        {
            System.out.println(container.get(i));
        }*/


        //http://www.sanfoundry.com/java-program-implement-heap-sort/


    }

      public static void swap(Vector<Integer> container, int i, int j)
      {
            /*int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;*/

          int tmp = container.get(i);
          container.set(i, container.get(j));
          container.set(j, tmp);

      }   

      public static void maxheap(Vector<Integer> container, int i) //ensure max number is the parent
        { 
            int left = 2*i ;
            int right = 2*i + 1;
            int max = i;
            if (left <= heapsize && container.get(left) > container.get(i));
                max = left;
            if (right <= heapsize && container.get(right) > container.get(max))        
                max = right;

            if (max != i)
            {
                swap(container, i, max);
                maxheap(container, max);
            }
        } 

        public static void heapify(Vector<Integer> container)  //built a heap
        {
            heapsize = container.size()-1;
            for (int i = heapsize/2; i >= 0; i--)
                maxheap(container, i);        
        }


        public static void sort(Vector<Integer> container)
        {       
            heapify(container);        
            for (int i = heapsize; i > 0; i--)
            {
                swap(container,0, i);
                heapsize = heapsize-1;
                maxheap(container, 0);
            }
        }  


}

I am have read a text file(ignore the 1st line of txt file , it indicates number of entries) which contains 10000 numbers into a Vector and tried to sort it but am getting the following error

java.lang.ArrayIndexOutOfBoundsException: Array index out of range: 19998

My debugger is not working as everytime i step over the function max heap , i get the source not found which has not been resolved.

I dont understand where the array out of bounds error is arising from , I have looked through the implementation code for the past 2 hours and cant find anything wrong with it , can someone tell me what is wrong with my code ??

Answer 1

You have a semicolon at the end of this line:

            if (left <= heapsize && container.get(left) > container.get(i));

Which means that the next line is always being run, and not only if the condition is true. take away the semi-colon and you're good to go!