當我投票時，PriorityQueue如何工作？

-1

我有一個名爲Pair的預定義類，其中包含一個鍵和一個值。我根據每對的價值的自然順序將它們存儲在PriorityQueue中。當我改變Pair中的一個值然後出隊時，我期望沒有發生。測試代碼如下。請幫忙。我感到困惑！當我投票時，PriorityQueue如何工作？

import java.util.*; 
public class Test { 
    static class Pair { 
     int key; 
     int value; 
     Pair (int key, int value) { 
     this.key = key; 
     this.value = value; 
     } 
    } 
    public static void main(String[] args) { 
     PriorityQueue<Pair> pq = new PriorityQueue<Pair>(3, new Comparator<Pair>() { 
     @Override 
     public int compare(Pair p1, Pair p2) { 
      return p1.value - p2.value; 
     } 
    }); 
    Pair p1 = new Pair(1, 31); 
    Pair p2 = new Pair(2, 32); 
    Pair p3 = new Pair(3, 33); 
    pq.offer(p1); 
    pq.offer(p2); 
    pq.offer(p3); 
    p2.value = 31; 
    p1.value = 32; 
    Pair p0 = pq.poll(); // It shows the reference p0 is p1 not expected p2. 
         // And what remain in pq are p2 with 31 and p3 with 33 
    } 
}

我知道PriorityQueue會在輪詢時排序項目。看起來我的例子中的PriorityQueue不起作用。

來源

2016-11-04 Walter Wang

你爲什麼期望p2？ –

「我知道PriorityQueue在投票時會對項目進行排序」< - 你真的嗎？ JavaDoc並沒有像方法輪詢那樣說，對我來說它看起來簡單的獲取輪詢方法並返回索引0處的當前對象，然後對隊列_after_進行排序。 –

@SotiriosDelimanolis我認爲p2的'value'（用於比較函數）是這三個'Pair'中的最小值，因此'PriorityQueue'應該用最小的'value'輪詢'Pair'，這是p2。 –

如果您有任何數據結構（如哈希映射/集合，TreeMap/Set或排序隊列，如PriorityQueue），如果您更改其中一個元素（特別是用於hashCode/equals/compareTo的字段取決於什麼方法），數據結構不知道要重新排列自己，而是你正在做的是破壞數據結構，因此它不能按預期工作。

簡而言之，您不能改變數據結構中對象的關鍵字段，並期望它以可靠的方式運行。

來源

2016-11-04 15:55:13

謝謝你的時間！我現在明白了。如果我想更新某個對象的優先級，我需要從'PriorityQueue'中刪除它，更改密鑰然後重新插入它，或者自己寫一個堆。 –

@WalterWang是的，你需要處理很多數據結構（數組和列表除外） –

當我投票時，PriorityQueue如何工作？

回答

相關問題