algorithm - 配列のリアルタイムソート

Question

これはインタビューの質問でした。

「株式に対して毎秒1000の入札を受け取ります。上位50の入札を保存し、平均を計算します。どのように？」

Answer 1

「リアルタイムソート」はしません。これまでの上位50件の入札のヒープ（優先キュー）データ構造を使用する可能性があります。次の入札が最小値を上回っている場合は、最小値を削除してから、新しい入札額を挿入します。優先キューを使用すると、最小値をすばやく見つけて削除し、新しい値を追加できます。

新しい入札と離脱入札の差の1/50を加算することで、平均値を維持できます（新しい入札が50番目に高い入札よりも優れている場合のみ）。