優先キューを表すバイナリヒープを作成しました。これは、古典的なよく知られたアルゴリズムです。このヒープは、さまざまなイベントの時系列シーケンスをスケジュールします（ソートキーは時間です）。
挿入と削除の2つの操作をサポートします。ヒープの各ノードのキーは、その子のそれぞれ以上です。ただし、同じキーでイベントを追加しても、追加された順序は保持されません。これは、削除または挿入が呼び出された後、ヒープアップおよびヒープダウンプロシージャが順序を壊すためです。
私の質問は、同じ優先順位を持つノードの順序を維持するために、従来のアルゴリズムで何を変更する必要があるかということです。
1 つの解決策は、挿入された要素に挿入時間属性を追加することです。これは、新しい要素がヒープに挿入されるたびにインクリメントされる単純なカウンターである可能性があります。次に、2 つの要素の優先順位が等しい場合、挿入の時間を比較します。
私の知る限り、ヒープは順序を維持するために構築されることはありません (これが、「ヒープ ソート」が安定したソートではないことで注目に値する理由です)。
あなたが求めているのは、小さなアルゴリズムのトリックでこれを変更できるかどうかということです (これは、古き良き信頼できる「タイムスタンプ」ソリューションではありません)。ありえないと思います。
私が提案したのは、これのいくつかのバージョンです：
同じ「挿入」を維持します。
「削除」を変更して、特定の優先度の要素で特定の順序が保証されるようにします。
これを行うには、ヒープダウンで、順序が保持されるまで要素を下にスワップするのではなく、同じ値の要素の樹枝状の終わりになるまで要素を下にスワップし、可能な場合は常に右に移動することを選択します。
残念ながら、これに関する問題は、指定された優先度の要素を挿入がどこに追加するかわからないことです。ツリーのどこにでも配置される可能性があります。これを変えることは、単なる構造の微調整以上のものになると私は信じています。
要素が時系列で挿入され、この順序が維持されている場合（たとえば、「挿入」ではなく「追加」、「削除」ではなく「remove_and_pack」を使用）、メモリアドレスを使用できます（符号なし32にキャスト）または、環境に応じて64ビット整数）を最終比較ステップとして要素に割り当てます。初期の要素は、後の要素よりも数値的に低いアドレスを持ちます。