Java中的優先級隊列

Question

你可以有2個參數嗎？例如，我想添加一個字符串和一個相應的整數到一個優先鍵。然後，我將按整數對它進行排序。我知道如何添加一個字符串或整數，但我不知道如何添加兩個。有人能指點我正確的方向，並讓我知道，如果我甚至以這種正確的方式進行？

Answer 1

如果你想使用多個元素作爲一個鍵，就可以創建一個封裝了一個類，然後使用該類型的關鍵。同樣的值。您應該使用此自定義密鑰類Comparable，覆蓋equals()，並覆蓋您創建的自定義密鑰類的hashCode()。

Answer 2

如何創建一個包含這兩個字段（int和String），然後執行Comparable（在INT場比較）一新類。不要忘了還覆蓋hashCode()和equals()（見後面重寫這些方法的推理Comparable javadoc類別）。

是你所追求的？

Answer 3

有兩種方法可以做到這一點。無論哪種方式，您都希望創建一個既包含String（所需值）又包含整數（優先級）的自定義對象。

第一個解決方案是有此數據對象實現Comparable：

class Data implements Comparable<Data> { 
    private final String message; 
    private final int priority; 

    public Data(String message, int priority) { 
    this.message = message; 
    this.priority = priority; 
    } 

    @Override 
    int compareTo(Data other) { 
    return Integer.valueOf(priority).compareTo(other.priority); 
    } 

    // also implement equals() and hashCode() 
} 

然後當你做

PriorityQueue<Data> queue = new PriorityQueue<Data>(); 

隊列將責令由compareTo方法定義的訂單項目。

這種解決方案的問題是，如果你想排序是僅在整數，然後要麼equals方法和你compareTo方法不會是一致的或者你equals方法是不正確的。

一個更好的解決辦法是使用PriorityQueue構造函數，一個Comparator。在這種情況下，Data將不必執行Comparable;你只需要一個Comparator定義您的訂購：

public final class OrderDataByPriority implements Comparator<Data> { 
    public static final OrderDataByPriority INSTANCE = new OrderDataByPriority(); 

    private OrderDataByPriority() {} 

    @Override 
    public int compare(Data data1, Data data2) { 
    return Integer.valueOf(data1.priority).compareTo(data2.priority); 
    } 

    @Override 
    public boolean equals(Object other) { 
    return other == OrderDataByInteger.INSTANCE; 
    } 

    private Object readResolve() { 
    return INSTANCE; 
    } 
} 

注意，因爲這比較不帶任何數據，我做了一個單例。

然後，您可以創建隊列行這樣的：

PriorityQueue<Data> queue = new PriorityQueue<Data>(
    initialCapacity, OrderDataByPrority.INSTANCE); 

Answer 4

這裏是做這件事的一般方法：

public class PriorityQueue<T> { 

    private java.util.PriorityQueue<IntPriorityComparableWrapper<T>> queue; 

    public PriorityQueue() { 
      queue = new java.util.PriorityQueue<IntPriorityComparableWrapper<T>>(); 
    } 

    public void add(int priority, T object) { 
      queue.add(new IntPriorityComparableWrapper<T>(object, priority)); 
    } 

    public T get() { 
      return (null != queue.peek())? queue.poll().getObject() : null; 
    } 


    /** 
    * A "wrapper" to impose comparable properties on any object placed in the 
    * queue. 
    */ 
    private static class IntPriorityComparableWrapper<T> 
    implements Comparable<IntPriorityComparableWrapper<T>> { 

      private T object; 
      private int priority; 

      public IntPriorityComparableWrapper(T object, int priority) { 
        this.object = object; 
        this.priority = priority; 
      } 

      public int compareTo(IntPriorityComparableWrapper<T> anotherObject) { 
        return this.priority - anotherObject.priority; 
      } 

      public int getPriority() { 
        return priority; 
      } 

      public T getObject() { 
        return object; 
      } 
    } 

}