import java.util.Comparator;
public class PriQueue <T> {
int defaultsize = 2000;
int size;
T[] elements;
int length;
Comparator<? super T> comparator;
@SuppressWarnings("unchecked")
public PriQueue(int size){
this.size = size;
if( size <= 0 ){
this.size = this.defaultsize;
}
this.elements = (T[]) new Object[size+1];
this.length = 0;
}
@SuppressWarnings("unchecked")
public PriQueue(){
this.size = this.defaultsize;
this.elements = (T[]) new Object[size+1];
this.length = 0;
}
public int size(){
return this.size;
}
public int length(){
return this.length;
}
public void setComparator(Comparator<? super T> comparator){
this.comparator = comparator;
}
void swap(int i, int j){
T t = elements[i];
elements[i] = elements[j];
elements[j] = t;
}
public void insert(T t){
int cur, parent;
if( this.length == this.size ){
throw new UnsupportedOperationException("queue is full");
}
if( comparator == null ){
throw new UnsupportedOperationException("Comparator is not defined.");
}
elements[++this.length] = t;
for( cur = this.length; cur > 1 &&
comparator.compare(elements[parent = cur/2], elements[cur])>0; cur=parent){
swap(parent,cur);
}
}
public T extractmin(){
int cur, child;
if( this.length < 1 ) {
return null;
}
if( comparator == null ){
throw new UnsupportedOperationException("Comparator is not defined.");
}
T t = elements[1];
elements[1] = elements[this.length--];
for( cur = 1; (child=2*cur)<=this.length; cur = child ){
if( (child+1) <= this.length &&
comparator.compare(elements[child+1], elements[child])< 0 ){
child++;
}
if( comparator.compare(elements[cur], elements[child])<=0 ){
break;
}
swap(cur, child);
}
return t;
}
}
Test:
public class TestMain {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
PriQueue<Integer> queue = new PriQueue<Integer>();
queue.setComparator(comp);
queue.insert(5);
queue.insert(3);
queue.insert(6);
queue.insert(2);
Integer val = null;
while( (val = queue.extractmin()) != null ){
System.out.print(val + " ");
}
}
}
Output: 2 3 5 6