Java priority queue help needed

Question

I am working on a traveling salesman problem here and my p-queue isn't operating it is simply taking the last item added. I was wonder if anyone could help me figure out the error. here is my Node class (nodes which are added to the queue):

import java.util.*; 

public class Node implements Comparable< Node >{

    //level of node
    int level;
    //stores path of node
    ArrayList< Integer > path = new ArrayList< Integer >();
    //bound of node
    int bound;

    /** Over-rides compareTo for priority queue handling
       * @return int desired sorting value
       */
    public int compareTo(Node aNode) 
    {               
      if (this.bound<aNode.bound)
      {
          return 1;
      }
      if (this.bound>aNode.bound)
      {
          return -1;
      }
      else
      {
          return 0;
      }
    }
}

and here is the p-queue implementation:

PriorityQueue< Node > theQ = new PriorityQueue< Node >();

The algorithm is implemented correctly the p-queue simply is not putting the lowest bound as the head. I even reversed the the returns on the compareTo with no effect on the p-queue output (signifying to me that the queue is not sorting. I have wasted hours trying to figure it out and also asking some classmates (no-one can discern the problem) taking a shot here to see if anyone knows why the queue is acting like this..

Define "p-queue output" ... do you mean if you iterate through the queue it's not in the order you expect? How are you accessing the queue? — Brian Roach
– Brian Roach, Commented May 16, 2011 at 4:40
yes i poll the q and it outputs the last item added, its not sorting... — idkWATimDOIN
– idkWATimDOIN, Commented May 16, 2011 at 4:41
it'd be helpful if you posted the code where you are accessing the queue — Zach L
– Zach L, Commented May 16, 2011 at 4:50

Brian Roach · Accepted Answer · 2011-05-16 04:59:18Z

3

Your code works perfectly fine for me.

What I suspect you're doing is changing the the bound value of a single object and repeatedly adding it, giving you a queue full of the same object (lots of references to it) which of course has the single (last) value you set it to.

public static void main(String[] args)
{
    PriorityQueue< Node > theQ = new PriorityQueue< Node >();
    Node n = new Node();
    n.bound = 6;
    theQ.add(n);
    n = new Node();
    n.bound = 9;
    theQ.add(n);
    n = new Node();
    n.bound = 4;
    theQ.add(n);
    while ((n = theQ.poll()) != null)
        System.out.println("Bound = " + n.bound);
}

Output:

Bound = 9
Bound = 6
Bound = 4

edited May 16, 2011 at 4:59

answered May 16, 2011 at 4:51

Brian Roach

77k12 gold badges140 silver badges164 bronze badges

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

1 Comment

idkWATimDOIN Over a year ago

you nailed it sir, i was declaring my new node outside the necessary loop, your a life saver!! thank you very much

Zach L · Accepted Answer · 2011-05-16 04:46:24Z

Make sure you are iterating through the PriorityQueue by using the methods provided by the Queue interface, ex. remove to pop an element off the top. In pseudo code:

for each element in some other collection
  priorityQueue.add(element)

while priorityQueue is not empty
 Set node to priorityQueue.remove()
 Do stuff with node

If you are trying to iterate through a for-each loop or PriorityQueue.iterator:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

Alternatively, if you don't want to destroy/remove elements from your PriorityQueue to iterate in order, you could use, as the documentation suggests,

  Arrays.sort(pq.toArray())

Collectives™ on Stack Overflow

Java priority queue help needed

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related