gauravmunjal's blog

By gauravmunjal, 14 years ago, In English


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 (OFFERPOLLREMOVE() AND ADD) METHODS; LINEAR TIME FOR THE REMOVE(OBJECT) AND CONTAINS(OBJECT) METHODS; AND CONSTANT TIME FOR THE RETRIEVAL METHODS (PEEKELEMENT, 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/

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By gauravmunjal, 14 years ago, In English
I often write about my work and experiences at my blog http://aintmeekcoder.blogspot.com/

As of now the work includes Projects involving Spring Source, Google App Engine etc.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it