2
public class PriorityQueue<T> {
 private PriorityNode<T> head, tail;
 private int numItems;

 public PriorityQueue(){
  numItems = 0;
  head=null;
  tail=null;
 }


 public void add(int priority, T value){
      PriorityNode<T> newNode = new PriorityNode<T>(priority,value);

      if(numItems == 0){
       head = newNode;
       tail = newNode;
      }
      else{
       head.setNext(newNode);
       head = newNode;
      }



     }

    }

Where PriorityNode is defined as:

 public class PriorityNode<T> implements Comparable<T> {
     private T value;
     private PriorityNode<T> next;
     private int priority;

     public PriorityNode(int priority,T newValue){
      value = newValue;
      next = null;
      priority = 0;
     }

     public PriorityNode(T newValue){
      value = newValue;
      next = null;
      priority = 0;
     }

     public void setPriority(int priority){
      this.priority = priority;
     }

     public int getPriority(){
      return this.priority;
     }

     public T getValue(){
      return value;
     }

     public PriorityNode<T> getNext(){
      return next;
     }

     public void setNext(PriorityNode<T> nextNode){
      this.next = nextNode;
     }

     public void setValue(T newValue){
      value = newValue;
     }

           @Override
     public int compareTo(int pri) {
      // TODO Auto-generated method stub
        if(this.priority<pri){
           return -1;
        }
        else if(this.priority == pri){
           return 0;
         }
        else{
           return 1;
         }


     }


    }

I'm having a lot of difficulty using the Comparator here and implementing a priority queue - please point me in the right direction.

hammar
  • 138,522
  • 17
  • 304
  • 385
Kay
  • 845
  • 7
  • 21
  • 33
  • 1
    It's not entirely clear what your question is. What is the 'difficulty'? compile error? unexpected results? – Sean Owen Apr 25 '10 at 10:28

3 Answers3

3

Don't use a tree structure to implement a priority queue. Use a heap. It is more space-efficient, requires fewer memory allocations, and is O(log(N)) for most operations.

Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • That's true, but i'm trying to complete this type of implemntation before an examiner springs this on me . – Kay Apr 24 '10 at 02:14
3

Regarding the implementing of the comparator, implementing the Comparator<T> or Comparable<T> interface requires the public int compareTo(T o) method to be overridden.

In the example code given, the compareTo(T) method is not overridden (the compareTo(int) method is defined, but that is not the same method signature), therefore, it will probably lead to a compiler error.

coobird
  • 159,216
  • 35
  • 211
  • 226
-1

I think you are making it a bit too tough on yourself, a priority queue is efficiently implemented with array-based heaps: simpler and more efficient (read: contiguous memory areas).

Savino Sguera
  • 3,522
  • 21
  • 20