# Has anyone passed all test cases in C# ? Two Heap Method getting TLE using SortedDictionary

• Since .NET does not provide built-in PriorityQueue, I implemented my own using a SortedDictionary.
SortedDictionary is internally an RB tree, so accessing the min/max key and inserting/removing are all O(logN)
Also, I'm caching the median values, so FindMedian() is O(1) as you can see below.
However I keep getting TLE with the below code.
Has anyone managed to pass all the test cases in C# ?
Also please comment if you have any idea about how to implement a more efficient priority queue in C#

``````public class MedianFinder
{
// keeps the lower half of the numbers
PriorityQueue<double,int> maxHeap = new PriorityQueue<double, int>();

// keeps the greater half of the numbers
PriorityQueue<double, int> minHeap = new PriorityQueue<double, int>();

int count = 0;

// Keeping these two in separate variables so that FindMedian is O(1)
double maxHeapMax;
double minHeapMin;

// Adds a num into the data structure.
{
maxHeap.Enqueue(num, 0);

if (maxHeap.GetCount() - minHeap.GetCount() == 1 && minHeap.GetCount() > 0)
{
maxHeapMax = Math.Max(maxHeapMax, num);

if (maxHeapMax > minHeapMin)
{
maxHeap.PopMax();
minHeap.PopMin();

maxHeap.Enqueue(minHeapMin, 0);
minHeap.Enqueue(maxHeapMax, 0);
}
}

if (maxHeap.GetCount() - minHeap.GetCount() > 1)
{
minHeap.Enqueue(maxHeap.GetMaxKey(), 0);
maxHeap.PopMax();
}

maxHeapMax = maxHeap.GetMaxKey();
minHeapMin = minHeap.GetCount() == 0 ? 0 : minHeap.GetMinKey();

++count;
}

// return the median of current data stream
public double FindMedian()
{
if (count % 2 == 0)
{
return (maxHeapMax + minHeapMin) / 2.0;
}

return maxHeapMax;
}

public class PriorityQueue<T1,T2>
{
private SortedDictionary<T1, Queue<T2>> heap = new SortedDictionary<T1, Queue<T2>>();
private int count = 0;

public int GetCount()
{
return count;
}

public void Enqueue(T1 key, T2 item)
{
++count;

if (!heap.ContainsKey(key))
{
}

heap[key].Enqueue(item);
}

public T1 GetMinKey()
{
return heap.First().Key;
}

public T2 PopMin()
{
--count;

T1 minkey = heap.First().Key;
T2 item = heap[minkey].Dequeue();

if (heap[minkey].Count == 0)
heap.Remove(minkey);

return item;
}

public T2 PeekMin()
{
T1 minkey = heap.First().Key;
return heap[minkey].Peek();
}

public T1 GetMaxKey()
{
return heap.Last().Key;
}

public T2 PopMax()
{
--count;

T1 maxkey = heap.Last().Key;
T2 item = heap[maxkey].Dequeue();

if (heap[maxkey].Count == 0)
heap.Remove(maxkey);

return item;
}

public T2 PeekMax()
{
T1 maxkey = heap.Last().Key;
return heap[maxkey].Peek();
}
}
}

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();