在內存中保存x最多/最不頻繁出現的keyvaluepair的方法

Question

我正在傳遞一系列keyvaluepair<string, uint>對，其中字符串表示一個值，而uint表示該值在源數據中出現的頻率。我需要能夠在內存中保存大部分/最不經常出現的值以及其頻率。

x在這種情況下應該相當小，但我可能需要檢查幾百萬雙。請注意，我無法改變我是如何通過對。

什麼是最好的方式去做這件事？我猜測有兩個數組可能是最好的選擇，並且隨着每個值的傳遞，根據數值，將其插入排序數組中，並將最小/最頻繁的值刪除。

Answer 1

這聽起來像你正在尋找priority queue數據結構。只需構建兩個，一個用於最常用的對，另一個用於最不常用的對，並動態填充它們和/或僅保留相關數量的值 - 這對於優先級隊列來說尤其容易。例如，要只保存十個最大的項目（僞代碼）：

PriorityQueue pq = new PriorityQueue(); 

foreach (var kvp in input) { 
    pq.Add(kvp); 
    if (pq.Count > 10) 
     pq.RemoveMin(); 
}