我需要一個數據結構,支持插入鍵值對,並使用最低鍵提取對。插入和提取可以在任何時候發生,因此數據結構必須保持連續排序,並且提取包括從列表中移除該對。此外,沒有新插入的對可以具有比最近提取的對的鍵低的鍵。隨着時間的推移,插入對的鍵值也會增加。排序數據結構:隨機輸入,最低輸出
要求:
- 鍵:64位無符號整數
- 在任何一個時間列出的條目的最大數目:〜10^6
- 條目每秒插入(和提取):〜10 ^被插入5
- 在提取後對
- 密鑰高效去除條目:當前最低鍵>鍵>當前最低鍵+ 10^7
- 個內存要求是不相關的,計算複雜度不
- 一些對可以具有相同的關鍵
到目前爲止,我還沒有嘗試過任何解決方案,但我對此有一些想法: – jms
@ user1062874那麼......您的想法是什麼? – ElKamina
將它實現爲小數組的循環緩衝區,然後簡單地遍歷循環緩衝區並對數組進行排序以獲得元素的順序。 +非常快速的插入 - 可能緩慢檢索最後一個元素 - 限制鍵的最大值 – jms