Sunday, July 8, 2012

Priority Queue implemented by heap

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