有効時間のスコアボード？

Question

私はスコアでソートされたn人の選手を含むスコアボードを維持したいと思っています。 プレイヤーがxポイントを獲得したとき（彼がまだトッププレイヤーでない場合）必要ならば彼の上のプレーヤーを交換してください。そして、私は彼の上のプレーヤーがスコアよりも大きいか、リストの一番上に来るまでこれを繰り返します。 これは、O（n）の最悪の場合の時間を持つ問題です.O（log n）のような形で行うことができますか？

Answer 1

balanced search treeを維持し、選手をスコアリングする。場合Z、

1. によってプレイヤNのスコアの変化は、Y

2. がN

3. のエントリを削除すると言う、Nの現在の値を見つけます

   nからへのマッピングを挿入y + z

複雑さは対数です。