Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Priority Queue Heap Incorrect Output & No File found Scanner

  1. #1
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Priority Queue Heap Incorrect Output & No File found Scanner

    Hi,

    I was having a problem with a null pointer exception originally, but I managed to fix that. Now however I am not getting the correct output for my PQ Heap.

    Firstly, I don't think they are being entered in correctly, and I have traced through my code for hours and I cannot figure out why.

    Secondly, when I try to use my "leave" function (to remove the root node) it only removes the first node over and over.
    For example, I input 4, 5 and 2, it goes in as (2, 5 ,4) and the output is (4, 4, 4).

    Thirdly, I am trying to read a file using scanner and input it into an adjacency list, however it cannot find the file. The file is in the same directory and it is spelt correctly

    Any help would be greatly appreciated!

    Here is my code for the PQ class:

    public class PQ
    {
      public Node[] array = new Node[30];
      public int max = 0;
     
      public PQ()
      {
     
      }
     
      //function to check if the PQ is empty, returns true if it is
      public boolean isEmpty()
      {
        if(array[1] == null)
          return true;
        else
          return false;
      }
     
      //function to add to the PQ
      public void enter(Node n)
      {
        max = max + 1;
     
        if(array[1] == null)
        {
          array[1] = n;
        }
     
        else
        {
        array[max] = n;
        }
     
        //System.out.println(max);
        balance(max);
      }
     
      //function to balance the PQ after an add
      private void balance(int count)
      {
        Node temp;
        if(array[2] == null && array[3] == null)
        {
          return;
        }
     
        else
        {
     
          while((array[count/2].key) > (array[count].key))
          {
            if(count == 1)
            {
              if(array[1].key > array[count].key)
              {
                temp = array[1];
                array[1] = array[count];
                array[count] = temp;
              }
     
              break;
            }
     
            //System.out.println("count:         " + count);
          //System.out.println("array count/2: " + array[count/2].key);
          //System.out.println("array count:   " + array[count].key);
     
            temp = array[count/2];
            array[count/2] = array[count];
            array[count] = temp;
     
            count = count/2;
            if(count == 1)
            {
              break;
            }
            count = count/2;
           // System.out.println("count:         " + count);
          }
        }
      }
     
      //function to remove from the PQ
      public Node leave()
      {
        Node temp;
     
        //check if array only has 1 node
        if(array[2] == null && array[3] == null)
        {
          temp = array [1];
          array[1] = null;
          max = max - 1;
          return temp;
        }
     
        else
        {
        temp = array [1];
          array[1] = array[max];
          array[max] = null;
          topBal(1);
          max = max - 1;
          return temp;
        }
        }
     
      //function to balance PQ after remove
      private void topBal(int temp)
      {
        Node temp2;
     
        if(array[1] == null)
          return;
     
        else
        {
          //only if right is null, if so check if left is greater, if so swap
          if(array[temp*2] != null && array[(temp*2)+1] == null)
          { 
            System.out.println("right null");
            if(array[temp*2].key > array[temp].key)
            {
             temp2 = array[temp]; 
             array[temp] = array[temp*2];
             array[temp*2] = temp2;
             topBal(temp*2);
            }
          }
     
           //only if left is null, if so check if right is greater, if so swap
          if(array[temp*2] == null && array[(temp*2)+1] != null)
          { 
            System.out.println("left null");
            if(array[(temp*2)+1].key > array[temp].key)
            {
             temp2 = array[temp]; 
             array[temp] = array[(temp*2) + 2];
             array[(temp*2)+1] = temp2;
             topBal((temp*2)+1);
            }
          }
     
          //if both are not null, check which is larger & if they are larger then current node, swap if so
          if(array[temp] != null && array[temp*2] != null && array[(temp*2) + 1] !=null)
          {
            System.out.println("both not null");
            //if left is larger
           if(array[temp*2].key > array[(temp*2)+1].key && array[temp*2].key > array[temp].key)
           {
             temp2 = array[temp];
             array[temp] = array[temp*2];
             array[temp*2] = temp2;
             topBal(temp*2);
           }
     
           //if right is larger
           if(array[temp*2].key < array[(temp*2)+1].key && array[(temp*2)+1].key > array[temp].key)
           {
             temp2 = array[temp]; 
             array[temp] = array[(temp*2) + 2];
             array[(temp*2)+1] = temp2;
             topBal((temp*2)+1); 
           }
          }
        }
      }
    }


    This is my code with the scanner and the output for the PQ:
    public class Dijkstras{
     
      AdjList list = new AdjList();
     
      public Dijkstras()
      { 
        Scanner filein;
       File in;  
        try{
       in = new File("A3_13f.dat");
       filein = new Scanner(in);
       collectData(filein);
      }
      catch(FileNotFoundException e)
      {
       System.out.println("No such file"); 
      }
     
     
        PQ p = new PQ();
     
        Node temp = new Node(4,(4+5), null);
        p.enter(temp); 
     
        Node temp1 = new Node(5,(2+5), null);
        p.enter(temp1);
     
        Node temp2 = new Node(2,(11+5), null);
        p.enter(temp2);
     
        System.out.println(p.array[1].key);
        System.out.println(p.array[2].key);
        System.out.println(p.array[3].key);
     
        //Node temp3 = new Node(1,(1+5), null);
        //p.enter(temp3);
     
        //Node temp4 = new Node(12,(12+5), null);
        //p.enter(temp4);
     
        //Node temp5 = new Node(17,(17+5), null);
        //p.enter(temp5);
        Node temp11;
        while(!p.isEmpty())
        {
     
          temp11 = p.leave();
          System.out.println(temp.key); 
        }
     
      }
     
      //function to collect all data from text file and place into AdjList
      public void collectData(Scanner filein)
      {
     
        while (filein.hasNext()) 
        {
          int u = filein.nextInt();
          int v = filein.nextInt();
          int w = filein.nextInt();
     
          list.fill(u,v,w);
        }
      }
     
      public static void main(String args[]) {new Dijkstras();}
    }


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Priority Queue Heap Incorrect Output & No File found Scanner

    Quote Originally Posted by OverZealous View Post
    Now however I am not getting the correct output for my PQ Heap.
    Please provide the output you do get, what input you used to get the output, and the output you expected to get.

    Quote Originally Posted by OverZealous View Post
    Firstly, I don't think they are being entered in correctly, and I have traced through my code for hours and I cannot figure out why.

    Secondly, when I try to use my "leave" function (to remove the root node) it only removes the first node over and over.

    Thirdly, I am trying to read a file using scanner and input it into an adjacency list, however it cannot find the file.
    For all three problems use a debugger (or printlns) to verify what happens as expected. At some point something is not what you expected. Do not rely on the human eye to notice a problem in the code, use the tools designed to find problems instead. If the code removes the first code over and over, go to the place where you expected the values to change to remove a different node, look at (or print out) the values of the variables until you find which one(s) have a value that is not correct. There are only so many reasons for a file not to be found. This should be a quick find and fix once you get a look at what is happening as it runs

  3. #3
    Junior Member
    Join Date
    Nov 2013
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: Priority Queue Heap Incorrect Output & No File found Scanner

    Quote Originally Posted by jps View Post
    Please provide the output you do get, what input you used to get the output, and the output you expected to get.

    For all three problems use a debugger (or printlns) to verify what happens as expected. At some point something is not what you expected. Do not rely on the human eye to notice a problem in the code, use the tools designed to find problems instead. If the code removes the first code over and over, go to the place where you expected the values to change to remove a different node, look at (or print out) the values of the variables until you find which one(s) have a value that is not correct. There are only so many reasons for a file not to be found. This should be a quick find and fix once you get a look at what is happening as it runs
    Thanks for the reply!

    This is my input
     Node temp = new Node(4,(4+5), null);
        p.enter(temp); 
     
        Node temp1 = new Node(5,(2+5), null);
        p.enter(temp1);
     
        Node temp2 = new Node(2,(11+5), null);
        p.enter(temp2);
     
        System.out.println(p.array[1].key);
        System.out.println(p.array[2].key);
        System.out.println(p.array[3].key);

    I expect the output to be 5,4,2

    but the output is:
    2, 5, 4


    Then when I use the leave function I expect to get 5, 4, 2
    But my output is 4, 4, 4

    Here is the code
    Node temp11;
        while(!p.isEmpty())
        {
     
          temp11 = p.leave();
          System.out.println(temp.key); 
        }
     
      }

    I very much appreciate your advice, I will continue to look for the errors using your advice.

    Thanks again!

Similar Threads

  1. [SOLVED] Priority Queue Null Pointer Exception
    By OverZealous in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 14th, 2013, 02:52 PM
  2. Priority Queue help
    By BuhRock in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 3rd, 2011, 06:37 PM
  3. generate priority queue from hashmap help
    By Scotty33 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 23rd, 2011, 09:32 PM
  4. Implementing a priority queue using a max heap
    By jsinclair1482 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 15th, 2011, 11:56 AM
  5. Priority Queue using comparable
    By jkalm in forum Collections and Generics
    Replies: 6
    Last Post: December 5th, 2010, 10:02 PM