望ましいのは、一連の数値を並べ替えたままにすることです (昇順または降順ですが、以下の例では昇順のみを示しています)。最高速度のデータ構造表現が問題です。
たとえば、ネットワークを介して、多くの異なる監視エージェントから数値のパケットを継続的に取得する集計プログラムを考えてみましょう。アイデアは、それらを常に高速にソートしておくことです。例として、次のパケットを順番に取得できます (int を使用しますが、実際には double が使用されます)。
A = [1, 3, 4, 6]
B = [1, 2, 3]
C = [2, 3, 5]
A = [2, 4, 7, 8]
等々。最初のパケットの後、アグリゲーターのデータ構造は既にソートされています (データ構造は、ソートの各数値が参照するソースを記憶しています)。
[1, 3, 4, 6] => イベント
次のパケットの後、それは新しいソースであるため、データ構造は次のようになります
[1, 1, 2, 3, 3, 4, 6] => イベント
次のパケットの後、
[1, 1, 2, 2, 3, 3, 3, 4, 5, 6] => イベント
A が新しいパケットを送信したため、A の古い値を見つけて新しい値に置き換え、最終的に新しい並べ替えを行う必要があります。置換と並べ替えは個別に行うことも、そうでないこともできます (インプレース)。目標は超高速です。
[1, 2, 2, 2, 3, 3, 4, 5, 7, 8] => イベント
2 番目の A を取得すると、ソートを維持しながら、すべての古い As を新しい As パケットに「置き換える」必要があることに注意してください。各パケットはデータ構造にソートされた後、コピーされ、「イベント」として送信される必要があります。これらのパケットは、マージソートアルゴリズムで数マイクロ秒ごとに猛烈かつ継続的に到着しています。
* これを行うのに最適なデータ構造は何ですか? Splay Tree か AVL ツリーでしょうか。*