当我投票时，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如何工作？

回答

相关问题