title: Why can't SortedSet be used as a Priority Queue or Min-Heap?
body: <p>I was attempting to solve the running median problem (on <a href="https://www.hackerrank.com/challenges/ctci-find-the-running-median" rel="nofollow noreferrer" title="hackerrank">hackerrank</a>) using a sorted set. Only it's elements don't appear properly sorted.</p>
  
  <p>See it in action here: <a href="http://rextester.com/NGBN25779" rel="nofollow noreferrer">http://rextester.com/NGBN25779</a></p>
  
  <pre><code>public class RunningMedian{
  
      List&lt;int&gt; list = new List&lt;int&gt;();
      SortedSet&lt;int&gt; sorted = new SortedSet&lt;int&gt;();
  
      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 &lt; 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"));
      }
  }
  </code></pre>
  
  <p>For the most part the sorted set does work. However at larger input sizes it begins to give wrong answers. It may not be the optimal solution to the problem but I'm curious as to why it fails at all. C# doesn't have a min-heap / priority queue so why can't sorted sets be used as a substitute?</p>
  
  <p>*Edited to include full code from hackerrank.</p>
  
  <p>Here is an input file.
  Input
  <a href="http://textuploader.com/dovni" rel="nofollow noreferrer">http://textuploader.com/dovni</a></p>
  
  <p>Expected
  <a href="http://textuploader.com/dovnb" rel="nofollow noreferrer">http://textuploader.com/dovnb</a></p>
  
  <p>Output
  <a href="http://textuploader.com/dovwj" rel="nofollow noreferrer">http://textuploader.com/dovwj</a></p>
  
  <p>Conflicts appear near the end</p>
  
  <p>Expected
  (Skipping 1-364)
  54240.0
  54576.5
  54913.0
  54576.5
  54240.0</p>
  
  <p>Results
  (Skipping 1-364)
  54240.0
  54576.5
  54913.0
  54963.0
  54576.5</p>