6

プライオリティ キューに対して独自の比較関数を定義しましたが、比較関数には配列の情報が必要です。問題は、配列の値が変更されたとき、それが比較関数に影響を与えなかったことです。どうすればこれに対処できますか? コード例:

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static final int INF = 100;
    public static int[] F = new int[201];

    public static void main(String[] args){

        PriorityQueue<Integer> Q = new PriorityQueue<Integer>(201, 
            new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                    if (F[a] > F[b]) return 1;
                    if (F[a] == F[b]) return 0;
                    return -1;
                }
            });

            Arrays.fill(F, INF);
            F[0] = 0; F[1] = 1; F[2] = 2;
            for (int i = 0; i < 201; i ++) Q.add(i);
            System.out.println(Q.peek()); // Prints 0, because F[0] is the smallest
            F[0] = 10;
            System.out.println(Q.peek()); // Still prints 0 ... OMG
        }
   }
4

3 に答える 3

4

コンパレーターは、キューを変更したとき (つまり、アイテムを追加したとき) にのみ呼び出されます。その後、キューは何かが順序を変更したことを認識していないため、順序は同じままです。

このようなコンパレータを使用するのはかなり混乱します。ある時点で A と B の 2 つの値があり、A>B がある場合、誰もが A が B よりも大きいままであると予想します。この問題に対する優先キューの使用は間違っていると思います。

于 2013-02-06T20:44:55.260 に答える
3

したがって、本質的には、比較基準をオンザフライで変更することになります。これは、プライオリティ キュー コントラクトが提供する機能ではありません。これは場合によってはうまくいくように見えるかもしれませんが (たとえば、別のアイテムを削除または挿入するときにヒープがアイテムの一部をソートする可能性があります)、保証がないため、有効なアプローチではありません。

できることは、配列を変更するたびに、すべての要素を取り出して、元に戻すことです。これはもちろん非常に高価です ( O(n*log(n))) ので、おそらく作業を試みる必要があります配列の値をまったく変更しないように、設計の周りに配置します。

于 2013-02-06T20:44:49.950 に答える
2

追加ではなく、ピーク時にコンパレータを使用するPriorityQueueのカスタム実装を使用します。

public class VolatilePriorityQueue <T> extends AbstractQueue <T>
{
    private final Comparator <? super T> comparator;

    private final List <T> elements = new ArrayList <T> ();

    public VolatilePriorityQueue (Comparator <? super T> comparator)
    {
        this.comparator = comparator;
    }

    @Override
    public boolean offer (T e)
    {
        return elements.add (e);
    }

    @Override
    public T poll ()
    {
        if (elements.isEmpty ()) return null;
        else return elements.remove (getMinimumIndex ());
    }

    @Override
    public T peek ()
    {
        if (elements.isEmpty ()) return null;
        else return elements.get (getMinimumIndex ());
    }

    @Override
    public Iterator <T> iterator ()
    {
        return elements.iterator ();
    }

    @Override
    public int size ()
    {
        return elements.size ();
    }

    private int getMinimumIndex ()
    {
        T e = elements.get (0);
        int index = 0;

        for (int count = elements.size (), i = 1; i < count; i++)
        {
            T ee = elements.get (i);
            if (comparator.compare (e, ee) > 0)
            {
                e = ee;
                index = i;
            }
        }

        return index;
    }
}
于 2013-02-06T20:52:15.243 に答える