用戶評分排名，選擇正確的數據結構

Question

我有問題要解決。

我將繼續獲得userid分數更新。這是一個整數，另一個長。 我需要支持兩個操作。

1. add userid-score，並返回排名。 （根據分數）
2. 根據rand返回用戶ID。 （例如輸入：3，用id返回第三最高分）

我應該選擇什麼數據結構？ 我曾想過BST，它插入的速度很快。但不容易獲得Kth值。

Answer 1

您可以註釋任何樹結構，以便每個節點都將該子節點的數量存儲在該節點下方，並在修改樹結構時更新此節點。然後，當您想要查找第k個最高分時，使用存儲在每個節點下方的後代數目向下導航，以告知您是向左還是向右分支。

E.g.如果根目錄有兩個孩子，每個都有8個後代，那麼如果你想找到排名第一的球員，排名第一的球員就是最大的球員。

我寫了一些東西來支持這樣的樂趣，我基於https://en.wikipedia.org/wiki/Treap。它很可能是平衡的，但是需要比AVL或紅黑樹少得多的代碼。 （當然，如果你只想檢索前N個項目來顯示高分表，你完全不需要這個，因爲從BST中拉出前N項是相對容易的）。

Answer 2

您正在尋找Order statistic tree，作爲@mcdowella表示，其基本上任何Binary search tree或B tree，同時支持2個操作：

Select：找到第i個最小元素

Rank：找到的索引當所有元素都被排序時，由相應的值給出元素。

這些操作可以使用簡單的tree traversal輕鬆實現。

還有一個內置的GNU C++實現它可以在這裏閱讀更多關於它的信息：C++ STL: Policy based data structures.