2010-03-31 124 views
5

請原諒我,如果這是一個試用的問題,但我有點困難搞清楚。具有定製匿名比較器的Java優先級隊列

我目前有一個類節點,每個'節點'是迷宮中的一個正方形。我試圖實現A *算法,因此這些節點中的每個節點都會有一個f-cost(int)數據成員。我想知道是否有辦法可以創建這些節點的優先級隊列,並將f-cost變量設置爲比較器?

我在網上看了一些例子,但我能找到的都是字符串優先級隊列。我可以爲節點類實現比較器嗎?這會允許我訪問存儲在其中的數據成員嗎?

非常感謝!

回答

8

絕對如此。

您可以使用基於匿名Comparator傳遞給構造一個PriorityQueue

int initCapacity = 10; 
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() { 
    public int compare(Node n1, Node n2) { 
     // compare n1 and n2 
    } 
}); 
// use pq as you would use any PriorityQueue 

如果您Node類已經實現了Comparable你甚至都不需要定義一個新的Comparator,作爲訂貨會默認使用。除了任何其他方法,對象之間的自然順序將被使用。

+0

謝謝!看起來我只是在計算覆蓋位時有點困難,你已經說清楚了! – Bharat 2010-03-31 18:22:51

1

從Javadoc中:

根據 級堆的極大優先級隊列。根據在構造時指定的順序 ,其 是根據比較器

另外指定或者根據它們的 自然順序(參見Comparable),或 此隊列訂單 元件,PriorityQueues支持通用的數據類型。因此,如果您在Node類中實現了Comparable,那麼您可以創建一個PriorityQueue<Node>並正常使用它。

或者,還有一個構造函數PriorityQueue(int initialCapacity, Comparator<? super E> comparator),它將比較器作爲PriorityQueue構造函數的一部分。如果您更喜歡這種方法,那麼在繼承Comparable時,您的節點類不需要包含額外的代碼。

0

java.util中有一個PriorityQueue類。你可以使用它,它將使用自然排序(Node實現Comparable)或者在構造函數中提供的比較器(如果不需要Node類中的代碼)。任何類都可以訪問另一個數據,只要你允許它通過使字段非私有(可能是不好的OOP風格)或提供訪問方法public int getG(),public int getH(),public int getF() 。

1
public class Node implements Comparable<Node>{ 

    public int compareTo(Node o) { 
     // your comparative function 
     return 0; 
    } 

}

如果的compareTo返回一個負的INT,它的意思是 「小於」,0表示 「等於」,1表示 「大於」

一個功能是所有你需要能夠使用PriorityQueue。

編輯:比較是其他方式,我搞砸了。-1 < | 0 = | 1>我alreays由於某種原因閱讀這些權利。

+0

謝謝!除了比較位以外,我的工作進展非常順利,而+ ve,-ve也說得很清楚。 愛侵略者Zim avatar btw ^^ – Bharat 2010-03-31 18:25:27

+1

要小心,比較結果是「倒退」:排名較低的值先返回。如果你認爲優先級隊列是一個按升序排序的列表是有意義的,但是當我第一次使用一個列表時,它讓我感到困惑,因爲我預期優先級爲100的元素顯然「高於」一個優先級30 ...;) – TMN 2010-03-31 18:43:33