排序數據結構：隨機輸入，最低輸出

我需要一個數據結構，支持插入鍵值對，並使用最低鍵提取對。插入和提取可以在任何時候發生，因此數據結構必須保持連續排序，並且提取包括從列表中移除該對。此外，沒有新插入的對可以具有比最近提取的對的鍵低的鍵。隨着時間的推移，插入對的鍵值也會增加。排序數據結構：隨機輸入，最低輸出

要求：

鍵：64位無符號整數
在任何一個時間列出的條目的最大數目：〜10^6
條目每秒插入（和提取）：〜10 ^被插入5
在提取後對
密鑰高效去除條目：當前最低鍵>鍵>當前最低鍵+ 10^7
個內存要求是不相關的，計算複雜度不
一些對可以具有相同的關鍵

來源

2013-07-25 jms

到目前爲止，我還沒有嘗試過任何解決方案，但我對此有一些想法： – jms

@ user1062874那麼......您的想法是什麼？ – ElKamina

將它實現爲小數組的循環緩衝區，然後簡單地遍歷循環緩衝區並對數組進行排序以獲得元素的順序。 +非常快速的插入 - 可能緩慢檢索最後一個元素 - 限制鍵的最大值 – jms

與其他人所建議的一樣，二進制堆是一個很好的選擇。我發現它們在大多數情況下表現都很好。 A d-ary heap（其中和爲3或4），可以提供10％的性能提升，但實現複雜性很小。在我所談論的堆大小的實驗中，3堆堆明顯比二進堆（2堆堆）快。

另一個選項是skip list，它會給你O（log n）插入和O（1）刪除最低。實現一個跳過列表比二進制堆稍微複雜一些，它需要更多的內存，常數因子更高。插入可能會比堆中稍微慢一點，但移除會顯着加快。無論是否足夠快地彌補額外的內存成本和增加的實現複雜性，您都必須自己回答。

來源

2013-07-25 22:10:43

提及跳過列表的+1。我完全忘了這些，他們肯定會爲這個項目尋找價值 – wlyles

一種選擇是priority queue，滿足您的要求---中，最低出是隨機的，它執行O(logn)插入並刪除（流行）。

來源

2013-07-25 20:50:02 keelar

您所描述的聽起來很像priority queue，優先級由關鍵比較確定。

理想的實現將是一個binary heap，因爲這會導致O(log n)插入和刪除，這將是更好的整體比一個是O(1)，另一個是O(n)。如果您希望插入或移除的次數很少，您可以使用已排序或未排序的順序來執行，但我仍然猶豫如此。就要求插入元素的鍵大於最後一個被刪除的元素而言，這隻需要一個額外的成員變量來指示最後一個被刪除的鍵的值;每次刪除時只更新一次。這樣做不會影響漸近運行時。或者，在調用插入方法之前，您可以在代碼中使用一個變量來檢查插入候選項。無論採用哪種方式，您都需要存儲上次移除的元素的鍵值，並在調用insert方法之前將其與插入的元素進行比較。

來源

2013-07-25 20:55:22 wlyles

排序數據結構：隨機輸入，最低輸出

回答

相關問題