爲什麼不能使用SortedSet作爲優先級隊列或Min-Heap？

Question

我正在嘗試使用排序集來解決運行中值問題（在hackerrank上）。只有它的元素沒有正確排序。

看到它在這裏的行動：http://rextester.com/NGBN25779

public class RunningMedian{ 

    List<int> list = new List<int>(); 
    SortedSet<int> sorted = new SortedSet<int>(); 

    public void Add(int num){ 
     list.Add(num); 
     sorted.Add(num); 
    } 
    public double MedianNotWorking(){ 
     return GetMedian(sorted.ToArray()); 
    } 
    public double MedianWorking(){ 
     int[] arr = list.ToArray(); 
     Array.Sort(arr); 
     return GetMedian(arr); 
    } 
    public double GetMedian(int[] arr){ 
     int idx = list.Count/2; 
     if(arr.Length % 2 == 0){ 
      return (double)((double)(arr[idx] + arr[idx-1])/2); 
     }else{ 
      return arr[idx]; 
     } 
    } 

} 

static void Main(String[] args) { 
    int n = Convert.ToInt32(Console.ReadLine()); 
    int[] a = new int[n]; 

    RunningMedian heap = new RunningMedian(); 
    for(int i = 0; i < n; i++){ 
     a[i] = Convert.ToInt32(Console.ReadLine()); 
     heap.Add(a[i]); 

     //double median = heap.GetMedian(); 
     double median = heap.MedianNotWorking(); 
     Console.WriteLine(median.ToString("F1")); 
    } 
} 

對於有序集合不工作的大部分。然而，在較大的輸入尺寸下，它開始給出錯誤的答案。這可能不是問題的最佳解決方案，但我很好奇它爲什麼失敗。 C＃沒有min-heap/priority隊列，那麼爲什麼不能使用排序的集合作爲替代？

*編輯爲包含hackerrank的完整代碼。

這是一個輸入文件。 輸入 http://textuploader.com/dovni

預期 http://textuploader.com/dovnb

輸出 http://textuploader.com/dovwj

衝突出現近終點

預期 （跳過1-364） 54240.0 54576.5 54913.0 54576.5 54240.0

結果 （跳過1-364） 54240.0 54576.5 54913.0 54963.0 54576.5

Answer 1

SortedSet集合根據定義僅唯一值包含。但是，您的輸入文件包含數字21794兩次，這意味着第二個21794條目不會被添加到您的SortedSet。所以你的排序集將包含比你的列表更少的值，你的整個算法不再工作。