Java PriorityQueue перестраивается, когда я меняю ключ записи? - PullRequest
Новая
       10

Java PriorityQueue перестраивается, когда я меняю ключ записи?

0 голосов
/ 04 июня 2018

Предположим, у меня есть очередь с приоритетами 

class Node{
        public int id;
        public int dist = Integer.MAX_VALUE;
        public Node(int id) { this.id = id; }
}

Queue<Node> q = new PriorityQueue<>((a, b) -> Integer.compare(a.dist, b.dist));

Тогда, если я это сделал (предположим, один / два являются объектами узлов) 

Node one = new Node(1);
Node two = new Node(2);
one.dist = 1;
two.dist = 2;
q.offer(one);
q.offer(two);
two.dist = -1;

Каково будет поведение очереди?two появится раньше?

Спасибо!

1 Ответ

0 голосов
/ 04 июня 2018

Различные реализации Java API могут вести себя по-разному.Но в отношении OpenJDK: нет.Такие операции, как peek, не пересортируют коллекцию: они просто возвращают первое значение в уже отсортированной коллекции.Таким образом, если вы не используете метод очереди, он не может знать, что порядок изменился.

На самом деле даже вызов add (например) не будет прибегать к существующим элементам: он предполагает, что существующие элементыотсортировано по мере перемещения нового элемента в нужное место в очереди.

См. исходный код из реализации openJDK.

...