Using a priority queue in Java

Question

Forgive me if this is a tried question, but I'm having a little difficulty figuring it out.

I currently have a class Node, and each 'node' is a square in a maze. I'm trying to implement the A* algorithm, so each of these nodes will have an f-cost (int) data member inside of it. I was wondering if there's a way that I can create a priority queue of these nodes, and set up the f-cost variable as the comparator?

I've looked at examples online, but all I can find are String priority queues. Can I implement Comparator for the Node class? Would this allow me to access the data member stored inside it?

Many Thanks!

Answer 1

From the Javadocs:

An unbounded priority queue based on a priority heap. This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator

Furthermore, PriorityQueues support generic data types. Therefore, if you implement Comparable in your Node class, then you can create a PriorityQueue<Node> and use it normally.

Alternately, there is a constructor PriorityQueue(int initialCapacity, Comparator<? super E> comparator) that takes in a Comparator as part of the PriorityQueue constructor. If you prefer this method, your node class does not need to contain the extra code needed when inheriting Comparable.

Answer 2

There is a PriorityQueue class in java.util. You can use that and it will either use natural ordering (Node implements Comparable) or a comparator supplied in the constructor (if you don't want that code inside your Node class). Any class can access any data inside another as long as you allow it either by making a field non-private (potentially bad OOP style) or supplying an accessor method public int getG(), public int getH(), public int getF().

Answer 3

Absolutely.

You can use a PriorityQueue based on an anonymous Comparator passed to the constructor:

int initCapacity = 10;
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() {
    public int compare(Node n1, Node n2) {
        // compare n1 and n2
    }
});
// use pq as you would use any PriorityQueue

If your Node class already implements Comparable you don't even need to define a new Comparator, as that order will be used by default. Barring any other method, the natural ordering between objects will be used.

Answer 4

public class Node implements Comparable<Node>{

    public int compareTo(Node o) {
         // your comparative function
         return 0;
    }

}

if compareTo returns a negative int, it means "less than", 0 means "equals", 1 means "greater than"

that one function is all you need to be able to use PriorityQueue.

EDIT: comparison is other way, i messed that up. -1 < | 0 = | 1 > i alreays read those right to left for some reason.