1

C ++ std :: priority_queueは、部分的な順序が必要です。しかし、その実装がバイナリヒープの場合、どのように機能しますか？( {a, b, c, x}, {c < b, b < a, c < a} )例：半順序集合があり、、、とxは何の関係もないと仮定aします。その場合、最大ヒープは次のようになります。bc

layer 1:    x
layer 2:  b   x
layer 3: x x a c

ポップ操作の後、教科書で一般的に見られる方法で、つまり、ルートを1に置き換え、cサイズを1つ減らします。次に、ルートの下にあるツリーをヒープ化する必要があります。

layer 1:    c
layer 2:  b   x
layer 3: x x a

交換cしbますc < bね。そして何？以来、まだ有効なヒープがありませんb < a。しかしb、「見る」ことはできませんa。

4

1 に答える 1

7

の要件は、コンパレータが厳密で弱い順序をpriority_queue定義することです（C ++標準の§23.6.4）。後者は§25.4/4で次のように定義されています。

厳密という用語は、非反射関係（！comp（x、x）for all x）の要件を指し、この用語は、全順序の要件ほど強くはないが、半順序の要件よりも強い要件に対して弱いという用語です。 。equiv（a、b）を！comp（a、b）&&！comp（b、a）と定義する場合、要件はcompとequivの両方が推移的な関係であるということです。

— comp（a、b）&& comp（b、c）はcomp（a、c）を意味します

— equiv（a、b）&& equiv（b、c）はequiv（a、c）を意味します[注：これらの条件下では、次のことを示すことができます。

i）equivは同値関係です

ii）compは、equivによって決定される同値類に明確な関係を誘導します

iii）誘導された関係は、厳密な全順序です。—エンドノート]

言い換えると、コンパレータで定義された関係は合計である必要はありませんが、仮想関係によって定義された同値類に関して合計である必要がありますequiv。これは、すべての要素をそれぞれより小さくも大きくも等しくないと定義します。他の。

さらに簡単に言えば、コンパレータ関係でカバーされていない要素はすべて等しいものとして扱われます。

于 2012-09-14T07:20:55.690 に答える