ソート対象が動的に変わる場合PriorityQueueが期待通りに動作しない

Javaでアルゴリズムの練習用プログラムを作成したところ、PriorityQueueが期待どおりに動作せず、盛大にハマってしまったので、自分用のメモを残しておきます。

状況

以下のようにキューからオブジェクトを取り出すごとに、キュー内オブジェクトの
ソートに使う値が動的に変わるプログラムを作成していました。

package my.algorithm.prim;

import my.algorithm.Vertex;
import my.algorithm.VertexConnection;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * {@link PriorityQueue}って、実はpoll対象の要素はソート対象から除外されてるのね・・・。
 * つまり、動的にソートに使用するキーが変わるようなオブジェクトの管理には向いていないっぽい。
 */
public class InvalidPrim {

    private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
        @Override
        public int compare(Vertex o1, Vertex o2) {
            System.out.println("compare: " + o1 + ", " + o2);
            return o1.getDistance() - o2.getDistance();
        }
    };

    void calculate(List<Vertex> vertices) {
        System.out.println("creation start");
        PriorityQueue<Vertex> unvisitVertices = new PriorityQueue<>(vertices.size(), VERTEX_COMPARATOR);
        for ( Vertex vertex : vertices ) {
            unvisitVertices.add(vertex);
        }
        System.out.println(unvisitVertices);

        System.out.println("iteration start");
        while ( ! unvisitVertices.isEmpty() ) {
            System.out.println("iteration...");
            System.out.println(unvisitVertices);

            Vertex target = unvisitVertices.poll();
            for (VertexConnection connection : target.getConnections() ) {
                Vertex toVertex = connection.getToVertex();
                boolean isAlreadyVisited = ! unvisitVertices.contains(toVertex);
                if ( isAlreadyVisited ) {
                    continue;
                }

                boolean smallerWeightFound = connection.getWeight() < toVertex.getDistance();
                if ( smallerWeightFound ) {
                    toVertex.setDistance(connection.getWeight());
                    toVertex.setPrev(target.getNumber());
                }
            }
        }
    }
}

しかし、実際に上記のプログラムを動かした時に表示されるprintlnの結果は以下のとおりでした。

creation start

compare: {number=1, distance=2147483647, prev=-1}, {number=0, distance=0, prev=-1}

compare: {number=2, distance=2147483647, prev=-1}, {number=0, distance=0, prev=-1}

compare: {number=3, distance=2147483647, prev=-1}, {number=1, distance=2147483647, prev=-1}

compare: {number=4, distance=2147483647, prev=-1}, {number=1, distance=2147483647, prev=-1}

[{number=0, distance=0, prev=-1}, {number=1, distance=2147483647, prev=-1}, {number=2, distance=2147483647, prev=-1}, {number=3, distance=2147483647, prev=-1}, {number=4, distance=2147483647, prev=-1}]

iteration start

iteration...

[{number=0, distance=0, prev=-1}, {number=1, distance=2147483647, prev=-1}, {number=2, distance=2147483647, prev=-1}, {number=3, distance=2147483647, prev=-1}, {number=4, distance=2147483647, prev=-1}]

compare: {number=1, distance=2147483647, prev=-1}, {number=2, distance=2147483647, prev=-1}

compare: {number=4, distance=2147483647, prev=-1}, {number=1, distance=2147483647, prev=-1}

iteration...

[{number=4, distance=4, prev=0}, {number=1, distance=2, prev=0}, {number=2, distance=2147483647, prev=-1}, {number=3, distance=8, prev=0}]

compare: {number=1, distance=2, prev=0}, {number=2, distance=2147483647, prev=-1}

compare: {number=3, distance=8, prev=0}, {number=1, distance=2, prev=0}

iteration...

[{number=1, distance=2, prev=0}, {number=3, distance=7, prev=4}, {number=2, distance=1, prev=4}]

compare: {number=2, distance=1, prev=4}, {number=3, distance=7, prev=4}

iteration...

[{number=2, distance=1, prev=4}, {number=3, distance=7, prev=4}]

iteration...

[{number=3, distance=5, prev=2}]

解説

上記の例では、「iteration...」の行が、pollの直前のキューの状態であり、その後の「compare: ...」の行が、pollした時にComparatorが出力するログになります。ログの内容を見ればわかりますが、pollされる先頭のオブジェクトはソート対象になっておらず、pollされた後のキュー内部のオブジェクトしかソートしないようです。ソートに使う項目が静的という過程ならば、上記の動作でソート回数を減らせますが、ソートに使う項目が動的に変わるとなると、先頭のオブジェクトをソートに使わない上記の動きには困ってしまいますね・・・。

参考情報

github上に上記のソースがおいてあります。

zyake/algorithm github