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


  • 0
    R

    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.
        public void AddNum(double num)
        {
            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.Add(key, new Queue<T2>());
                }
    
                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();
    // mf.AddNum(1);
    // mf.FindMedian();
    

  • 0
    C

    I implemented my own heap, and passed all test cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.