1

私はPriorityQueue自分のプログラムにを実装しています。そのために私も実装しcompareTo()ました。compareTo()演じるときに呼ばれているのですがadd()、これは期待通りです。でも、演奏するときにも呼ばれますpoll()。poll（）の機能は頭を取り除く
ことだと思いました。なぜcompareTo（）を呼び出す必要があるのですか？

4

2 に答える 2

3

優先キューの実装方法は、多くの場合、ヒープを使用して行われます。の一部はpoll()ing、要素を比較するためにヒープを必要とするヒープを再構築する必要があります...したがってcompareTo()。ただし、これは単なる推測です（つまり、主張を検証するためにソースコードを掘り下げていません）。

興味がある場合は、ヒープを使用して優先度付きキューを実装する方法を簡単に検索できます。http: //pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html#imp

実際、楽しみのために、これが厳密ではない方法でどのように機能するかを説明します。ヒープは、ヒーププロパティを満たすツリーです。親は常に子以下（最小ヒープ）であるか、親は常に少なくとも子と同じ大きさ（最大ヒープ）です。PriorityQueueミンヒープなのでpoll()ルートを削除します（これを理解していることを確認してください）。しかし、ルートを削除すると、ツリーはどうなりますか？それはもはやツリーではありません...したがって、これを修正する方法は、ツリーのルートをリーフノードに移動し（ツリーを破壊したり、ヒーププロパティを無効にしたりせずにプルできる）、他のノードを根。しかし、どのノードをルートに入れますか？直感的には、ルートの左または右の子を配置すると思うかもしれません（これらは「元のルートとほぼ同じくらい小さい」）。それは可能ですが、その子をルートとするサブツリーを修正する必要があります（コードは醜いです）。代わりに、（概念的には）同じことを行いますが、コードをより良くするために少し異なる方法で行います。特に、彼らはリーフノードを摘み取り、それをルートに貼り付けます（通常、ルートとリーフノードを交換して両方のステップを同時に実行します）。しかしヒーププロパティは必ずしも満たされていません（ルートにスタックしたリーフノードは非常に大きくなる可能性があります！）。これを修正するには、正しい場所に到達するまで新しいルートを「バブルダウン」します。具体的には、新しいルートを左右の子と比較し、ヒーププロパティが満たされるまで（親が子の少なくとも1つよりも大きい場合）スワッピングを続けます。このスワッピングは確かに有効なヒープにつながることに注意してください（これを証明することはできますが、直感的です）。

于 2012-11-18T12:45:56.387 に答える
2

すべてがJavaDocにあります（私の強調）：

優先度ヒープに基づく無制限の優先度キュー。

そして、あなたのソースコードにはpoll()次のものがあります。

public E poll() {
    //...
    if (s != 0)
        siftDown(0, x);
    return result;
}

どこsiftDown()にありますか：

/**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 * [...]
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

JavaDocのコメントsiftDown()は非常に重要です。注意深く読んでください。基本的に、の厄介な実装でPriorityQueueはヒープを使用します。ヒープは、ポーリングによって変更するたびに再構築する必要があります。

なぜあなたはこれに悩まされているのですか？compareTo()のように、軽量でべき等で副作用のない方法である必要がありますequals()。制限を加えるべきではありません。

于 2012-11-18T12:45:43.570 に答える