c# - 为什么 SortedSet 不能用作优先级队列或最小堆？

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# 没有最小堆/优先级队列，所以为什么不能使用排序集作为替代？

*经过编辑以包含来自 hackerrank 的完整代码。

这是一个输入文件。输入 http://textuploader.com/dovni

预计 http://textuploader.com/dovnb

输出 http://textuploader.com/dovwj

冲突出现在接近尾声

预计(跳过 1-364)54240.054576.554913.054576.554240.0

结果(跳过 1-364)54240.054576.554913.054963.054576.5

Answer 1

SortedSet 集合根据定义仅包含唯一值。但是，您的输入文件两次包含数字 21794，这意味着第二个 21794 条目不会添加到您的 SortedSet 中。因此，您的排序集包含的值将少于您的列表，并且您的整个算法不再有效。