PriorityQueue Implementation

While learning Dijkstra's I have come across this class PriorityQueue.

class PriorityQueue

It basically keeps the elemts sorted accordingly. The head of the queue is the least element to the specified ordering. Implementation note: this implementation provides O(log(n)) time for the insertion methods (offer, poll, remove() and add) methods; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

How will the sorting be done?

This is either naturally specified or otherwise, that depends on the arguments of the constructor. Like if the class Integer is specified then the comparison will be done using the compareTo method of the comparable interface. This is when we do 

PriorityQueue temp = new PriorityQueue();

For adding and removal the methods which are available are : add() and poll() (removes the element from the head of the Queue)

Program

public static void main(String[] args) {

PriorityQueue temp = new PriorityQueue();

temp.add(4); temp.add(2); temp.add(3); temp.add(7); temp.add(1);

while (!temp.isEmpty()) {

System.out.println(temp.poll());

}

}

Output

1

2

3

4

7

This being the case when we use a class which has already implemented the Comparable Interface. 

Now suppose that we have user defined objects to be stored in the PriorityQueue, then for the sorting to be done the user defined class will implement the interface Comparable and override the compareTo(Object c) method.

import java.util.PriorityQueue;

class Node implements Comparable{

public int a,b,c;

public void setA(int a) {

this.a = a;

}

public void setB(int b) {

this.b = b;

}

public void setC(int c) {

this.c = c;

}

public int compareTo(Node o) {

return new Integer(this.c).compareTo(o.c);

};

}

public class PQExample {

public static void main(String[] args) {

Node n = new Node();

n.setA(1);

n.setC(4);

Node n2 = new Node();

n2.setA(2);

n2.setC(6);

Node n3 = new Node();

n3.setA(3);

n3.setC(1);

PriorityQueue temp = new PriorityQueue();

temp.add(n); temp.add(n2);temp.add(n3);

while (!temp.isEmpty()) {

System.out.println(temp.poll().a);

}

}

}

Output

3

1

2

I learnt these concepts from Pratik Tandel (pt1989) ,  http://problemclassifier.appspot.com/