Java實現PriorityQueue - 當沒有比較器提供

我想在Java中使用二進制堆實現自己的通用PriorityQueue版本。我選擇爲我的堆使用Object數組。Java實現PriorityQueue - 當沒有比較器提供

Object[] qArray = new Object[initial_Size];

如果用戶提供了一個比較 - 實現是非常簡單的，因爲我可以用比較的方法進行比較時，我做我的元素比較。

Comparator<T> comparator; //Set to a user-provided comparator in my constructor. 

if(comparator.compare((T)qArray[i], (T)qArray[j]) 
    //do something

但是，問題出現在用戶不提供默認比較器時。我可能處理這個問題的方法之一是讓我的PriorityQueue類實現比較器和具有比較執行下列操作比較 -

@Override 
public int compare(T o1, T o2) 
{ 
    if(this.comparator == null) //no comparator provided by user 
    { 
     return o1.toString().compareTo(o2.toString()); 
    } 
    else 
    { 
     return this.comparator.compare(o1, o2); 
    } 
}

然而，這種比較是有點跛。它顯然適用於String類型的PriorityQueues，但在整數情況下（不會）（它會認爲5大於49）。另一種方法是強制用戶提供比較器 - 但我知道Java Util的PriorityQueue實現更友善。

因此，我嘗試反向工程Java的PriorityQueue一點點，並初始化自定義類類型的優先級隊列，而不通過比較器。

public class TestClass { 

    public class SomeClass 
    { 
     int value; 
     SomeClass(int value) 
     { 
      this.value = value; 
     } 
    } 

    public static void main(String[] args) 
    { 
     TestClass tClass = new TestClass(); 
     TestClass.SomeClass sClass1 = tClass.new SomeClass(10); 
     TestClass.SomeClass sClass2 = tClass.new SomeClass(20); 

     PriorityQueue<TestClass.SomeClass> pQueue = new PriorityQueue<TestClass.SomeClass>(); 
     pQueue.add(sClass1); 
    } 
}

StackTrace

所以這個siftUpComparable方法可能包含有關util包如何做它的一些比較重要的線索，但是當我試圖讀取源代碼，我迷路了。

因此，在這裏實現的任何想法 - 其中如果在提供的對象類型（如Integer或String）上定義了自然排序比較器，則應該默認使用它。

來源

2014-01-16 Hari

存儲一些接口的實現（如可比），而不是對象？ – John3136

Exception例外：Java嘗試將給定對象投射到Comparable，如果您沒有提供Comparator。

您不能將任意類型的對象與通用算法進行比較。這就是爲什麼您必須提供Comparator或確保您的對象支持compareTo方法並實施Comparable。

來源

2014-01-16 04:03:03 Domi

當你不及格比較，SomeClass應該實現Comparable接口即

public class SomeClass implements Comparable<Integer> 
{ 
    int value; 
    SomeClass(int value) 
    { 
     this.value = value; 
    } 
    public int compareTo(Integer o) { 
     ....... // Logic to compare 
    } 
}

來源

2014-01-30 05:52:46 Jayasagar

Java實現PriorityQueue - 當沒有比較器提供

回答

相關問題