Java：PriorityQueue從自定義比較器返回不正確的排序？

我寫了一個自定義比較器來比較我的節點類，但是java優先級隊列沒有以正確的順序返回我的項目。Java：PriorityQueue從自定義比較器返回不正確的排序？

這裏是我的比較：

public int compare(Node n1, Node n2){ 

    if (n1.getF() > n2.getF()){ 
     return +1; 
    } 
    else if (n1.getF() < n2.getF()){ 
     return -1; 
    } 
    else { // equal 
     return 0; 
    } 
}

凡GETF返回一個double。將幾個節點到優先級隊列後，但是，我打印出來使用：

while(open.size() > 0) { 
    Node t = (Node)(open.remove()); 
    System.out.println(t.getF()); 
}

導致：

6.830951894845301 
6.830951894845301 
6.0 
6.0 
5.242640687119285 
7.4031242374328485 
7.4031242374328485 
8.071067811865476

任何想法，爲什麼會這樣？我的比較器是否錯誤？謝謝。

Mike

來源

2010-06-15 Michael Simpson

實際的Java類是你的「java優先隊列」（我認爲是PriorityQueue），你是如何構造它的？ – Gray 2010-06-15 19:59:14

java.util.PriorityQueue，我假設？ – Ceilingfish 2010-06-15 20:00:10

不回答你的問題，但我注意到你可以簡化你的比較器： 'return Double.compare（n1.getF（），n2.getF（））;' – 2010-06-15 20:00:37

如何打印出這些值？我不認爲從PriorityQueue迭代器提供了整體類不相同的排序保證，所以潛在的，如果你正在做

for(Node n : queue) { 
System.out.println(n.getF()); 
}

你會得到無序的輸出。訂購保證僅適用於offer,take,poll,peek，以及可能的其他一些方法。

有在的Javadoc優先級隊列的迭代器特別提及http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

來源

2010-06-15 19:59:36 Ceilingfish

這是正確的;來自'iterator（）'方法的'PriorityQueue' javadoc：「迭代器不以任何特定順序返回元素。」 – 2010-06-15 20:02:50

「你是如何印出這些價值的？」......這個問題說「我用...印出來」。 – aioobe 2010-06-15 20:12:17

我沒有使用迭代器。比較器 comparator = new NodeComparator（）; PriorityQueue open = new PriorityQueue （INITIAL_SIZE，comparator）; 然後上面的while循環。 – 2010-06-15 20:38:11

不知道什麼是你的代碼錯誤，但是這對我的作品：

import java.util.*; 
public class Test { 
    public static void main(String[] args) { 
     PriorityQueue<Node> open = new PriorityQueue<Node>(10, 
       new Comparator<Node>() { 
      @Override 
      public int compare(Node n1, Node n2){ 
       if (n1.getF() > n2.getF()){ 
        return +1; 
       } 
       else if (n1.getF() < n2.getF()){ 
        return -1; 
       } 
       else { // equal 
        return 0; 
       } 
      } 
     }); 

     for (int i = 0; i < 20; i++) 
      open.add(new Node()); 

     while(open.size() > 0) { 
      Node t = (Node)(open.remove()); 
      System.out.println(t.getF()); 
     } 
    } 
} 

class Node { 
    double d = Math.random() * 10; 
    public double getF() { return d; } 
}

輸出：

0.21442281608773262 
1.9965384843480016 
2.6660026888929824 
2.888889937975976 
3.098932914222398 
3.1059072964534638 
4.193212975907516 
4.296282412431935 
4.3241392173963735 
4.825876226139123 
5.193550353435191 
5.637831708672641 
5.949759449054407 
6.620639629878806 
7.505126870725806 
7.966337123623846 
8.270840212631589 
8.484502118941545 
8.730910327480023 
9.191324325662219

確保getF()不會意外返回double的整型版本。

更新：您無法更新定義插入後元素順序的數據。在這種情況下，您需要提取元素並進行更新，然後重新插入元素。

來源

2010-06-15 20:02:17 aioobe

你可以嘗試使用類迭代器嗎？看看你是否得到無序的輸出？ – Ceilingfish 2010-06-15 20:04:03

然後它沒有正確排序。說得通。如果它是作爲堆實現的，它只知道下一個要移除的元素是哪個。 – aioobe 2010-06-15 20:07:14

嗯......我先將節點添加到prio隊列中，然後使用Node的「setF」函數更改f值。插入對象後，有沒有在prio隊列中更新值的問題？即使我指向prio隊列中的節點？ @Ceilingfish - 我的節點類將f值初始化爲-1，然後插入prio隊列，然後更新f val。這與你上面的例子不同。我很感謝你檢查基本邏輯，但謝謝。 – 2010-06-15 20:37:25

Java：PriorityQueue從自定義比較器返回不正確的排序？

回答

相關問題