Thread: 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();}
}

Originally Posted by OverZealous

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.

Originally Posted by OverZealous

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

Originally Posted by jps

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!