Priority Queues I

[chili5]

Priority Queues

A priority queue is similar to a Queue. Items are removed from the queue in a certain order. In a queue the order is FIFO (meaning first-in, first-out). The first item added to the queue is the first item to be removed from the queue.

A priority queue removes items in an order defined by a comparator. A comparator is an object that defines how objects should be ordered. You might have seen this is if you have looked at sorting objects.

Let us look at this compare to method:

public int compareTo(Golfer g) {
        if (g.nScore > nScore) {
            return -1;
        }

        if (g.nScore < nScore) {
            return 1;
        }

        return -g.sName.compareTo(sName);
    }

If we had objects in a priority queue that had this compareTo method, the next item removed would be the one with the lowest score. However, if the scores are equal, then the player in alphabetical order will be returned.

This is a nice way to do some sorting without actually calling Arrays.sort or Collections.sort.

Creating a Priority Queue

A priority queue is a generic class that can only hold objects. It is created like this:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

Adding to a Priority Queue

Adding an item is as simple as calling the .add method of the PriorityQueue class.

pq.add(5);
pq.add(4);
pq.add(8);
pq.add(12);
pq.add(1);
pq.add(-1);

Removing Items

We simply call the remove method and the next item is removed. The next item is determined by the comparator.

Try this code:

 while (!pq.isEmpty()) {
      System.out.println(pq.remove());
 }

The output is:

-1
1
4
5
8
12

Noticed, how it is sorted? This makes for a really great way to do some sorting.

Other uses?

Another use for this class is in implementing Dijkstra's Single Pair Shortest Path Algorithm. This is something I will discribe later. Basically Dijkstra's Algorithm allows us to find the shortest path between any two nodes. We would use a priority queue to choose the next node that is a shortest distance from the starting node.

It is called the Single Pair Shortest Path Algorithm because it finds all the shortest paths from a start node to all other nodes.

Dijkstra's Algorithm is just one use of this algorithm.

[Jordan]

Well written, +rep!

[BlaineSch]

Wonderful + Rep!

[ThemePark]

Cool, didn't know about priority queues or that Java had them. +rep

So the Djikstra algorithm you mention, can be used for approximating a solution to the TSP problem, right? If so, I'd love to see an article on that.

Edit:
Okay, so I have to spread some rep before I can give you any. Once I can +rep you again, I will.

[debtboy]

Good Tutorial +rep

[chili5]

Cool, didn't know about priority queues or that Java had them. +rep

So the Djikstra algorithm you mention, can be used for approximating a solution to the TSP problem, right? If so, I'd love to see an article on that.

Edit:
Okay, so I have to spread some rep before I can give you any. Once I can +rep you again, I will.

Thanks. I believe it can, I haven't looked at the TSP problem very much but doesn't it just come down to finding the shortest path from a city to some other city? http://nayuki.eigenstate.org/files/d...te200601p5.pdf

So yes, you can use Dijkstra's algorithm to get a solution for this problem. I'll do a write up later.

[WingedPanther]

Nice job. +rep