Implémentation Java priorité Queue

Question

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; 
     } 



    } 

    } 

Où PriorityNode est défini comme:

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; 
     } 


    } 


    } 

Je vais avoir beaucoup de difficultés à utiliser la mise en œuvre ici et Comparator une file d'attente prioritaire - s'il vous plaît me diriger dans la bonne direction. Ne pas utiliser une structure arborescente pour implémenter une file d'attente prioritaire.

Answer 1

Utilisez un heap. Il est plus économe en espace, nécessite moins d'allocations de mémoire et est O (log (N)) pour la plupart des opérations.

Answer 2

En ce qui concerne la mise en œuvre du comparateur, la mise en œuvre de l'interface Comparator<T> ou Comparable<T> nécessite le remplacement de la méthode public int compareTo(T o).

Dans le code exemple donné, la méthode compareTo(T) n'est pas surchargée (la méthode compareTo(int) est définie, mais qui est pas la même signature de méthode), par conséquent, cela conduira probablement à une erreur du compilateur.

Answer 3

Je pense que vous êtes un peu trop dur avec vous-même, une file d'attente prioritaire est implémentée efficacement avec des tas basés sur des tableaux: plus simple et plus efficace (lire: zones de mémoire contiguës).