Java Priority Queue Implementation

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 hard time compromising Comparator and implementing a priority queue - please point me in the right direction.

+2


a source to share


3 answers


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



+3


a source


As far as the implementation of the comparator is concerned, the implementation Comparator<T>

or Comparable<T>

is required for the method to public int compareTo(T o)

be overridden.



In the above code example, the method is compareTo(T)

not overridden (the method is compareTo(int)

defined, but it is not the same method signature), so it will likely result in a compiler error.

+3


a source


I think you are making this too harsh for yourself, the priority queue is efficiently implemented with arrays based on arrays: simpler and more efficient (read: contiguous memory regions).

-1


a source







All Articles