My Solution Along with Implementation of MaxHeap<T> and MinHeap<T> in C#


  • 0
    Y
    public class MedianFinder
    {
        MinHeap<int> minheap;
        MaxHeap<int> maxheap;
            
        /** initialize your data structure here. */
        public MedianFinder()
        {
            minheap = new MinHeap<int>();
            maxheap = new MaxHeap<int>(); ;
        }
    
        public void AddNum(int num) //Always trying to keep maxheap.Count>=minheap.Count
        {
            if (maxheap.Count == 0) maxheap.Insert(num);
            else if(maxheap.Count>minheap.Count)
            {
                if(num>=maxheap.Max) //it belongs to minheap, and there is enough space
                {
                    minheap.Insert(num);
                }
                else //it belongs to maxheap, but there is no enough space
                {
                    minheap.Insert(maxheap.ExtractMax());
                    maxheap.Insert(num);
                }
            }
            else if (maxheap.Count==minheap.Count)
            {
                if (num >= maxheap.Max) //it belongs to minheap, but there is no enough space
                {
                    maxheap.Insert(minheap.ExtractMin());
                    minheap.Insert(num);
                }
                else //it belongs to maxheap and there is enough space
                {
                    maxheap.Insert(num);
                }
            }
    
        }
    
        public double FindMedian()
        {
            int count = minheap.Count + maxheap.Count;
            if (count % 2 == 0) //if even, average of two middle ones
            {
                return Convert.ToDouble(minheap.Min + maxheap.Max) / 2;
            }
            else
                return maxheap.Max;
        }
    }
    
    class MaxHeap<T> where T:IComparable<T>
    {
        private List<T> Heap;
    
        public MaxHeap()
        {
            Heap = new List<T>();
        }
    
        public T Max
        {
            get
            {
                if (Heap.Count == 0) throw new NullReferenceException();
                else return Heap[0];
            }
        }
        public bool IsEmpty()
        {
            return Heap == null || Heap.Count == 0;
        }
    
        public int Count
        {
            get
            {
                if (Heap == null) return 0;
                else
                {
                    return Heap.Count;
                }
            }
        }
    
        public void Insert(T data)
        {
            Heap.Add(data);
    
            int ch = Heap.Count - 1; //ch for child
            while (ch > 0)
            {
                int p = (ch - 1) / 2; //p for parent
    
                if (Heap[ch].CompareTo(Heap[p]) > 0) //meaning child is bigger than parent -> Swap'm
                {
                    Swap(p, ch);
                    ch = p;
                }
                else
                    break;
            }
        }
    
        private void Swap(int p, int ch)
        {
            T temp = Heap[p];
            Heap[p] = Heap[ch];
            Heap[ch] = temp;
        }
    
        public T ExtractMax()
        {
            if (Heap == null || Heap.Count == 0) throw new NullReferenceException();
            T ret = Heap[0];
    
            Heap[0] = Heap[Heap.Count - 1];
            Heap.RemoveAt(Heap.Count - 1);
    
            Heapify(0);
    
            return ret;
        }
        private void Heapify(int i) //i is parent
        {
            int ch1 = 2 * i + 1; //left child
            int ch2 = 2 * i + 2; // right child
    
            if (ch1 >= Heap.Count && ch2 >= Heap.Count) return;
    
            int bigger = (ch2 >= Heap.Count) ? ch1 : (Heap[ch1].CompareTo(Heap[ch2]) > 0) ? ch1 : ch2;
            //if ch2 is out of boundary, ch1 is bigger, don't check rest, otherwise, see which one has bigger data
    
            if (Heap[i].CompareTo(Heap[bigger]) < 0)
            {
                Swap(i, bigger);
                Heapify(bigger);
            }
    
        }
    }
    
    class MinHeap<T> where T : IComparable<T>
    {
        private List<T> Heap;
    
        public MinHeap()
        {
            Heap = new List<T>();
        }
    
        public T Min
        {
            get
            {
                if (Heap.Count == 0) throw new NullReferenceException();
                else return Heap[0];
            }
        }
    
        public bool IsEmpty()
        {
            return Heap == null || Heap.Count == 0;
        }
    
        public int Count
        {
            get
            {
                if (Heap == null) return 0;
                else
                {
                    return Heap.Count;
                }
            }
        }
    
        public void Insert(T data)
        {
            Heap.Add(data);
    
            int ch = Heap.Count - 1; //ch for child
            while (ch > 0)
            {
                int p = (ch - 1) / 2; //p for parent
    
                if (Heap[ch].CompareTo(Heap[p]) < 0) //meaning child is smaller than parent -> Swap'm
                {
                    Swap(p, ch);
                    ch = p;
                }
                else
                    break;
            }
        }
        private void Swap(int p, int ch)
        {
            T temp = Heap[p];
            Heap[p] = Heap[ch];
            Heap[ch] = temp;
        }
    
        public T ExtractMin()
        {
            if (Heap == null || Heap.Count == 0) throw new NullReferenceException();
            T ret = Heap[0];
    
            Heap[0] = Heap[Heap.Count - 1];
            Heap.RemoveAt(Heap.Count - 1);
    
            Heapify(0);
    
            return ret;
        }
        private void Heapify(int i) //i is parent
        {
            int ch1 = 2 * i + 1; //left child
            int ch2 = 2 * i + 2; // right child
    
            if (ch1 >= Heap.Count && ch2 >= Heap.Count) return;
    
            int smaller = (ch2 >= Heap.Count) ? ch1 : (Heap[ch1].CompareTo(Heap[ch2]) < 0) ? ch1 : ch2;
            //if ch2 is out of boundary, ch1 is smaller, don't check rest, otherwise, see which one has smaller data
    
            if (Heap[i].CompareTo(Heap[smaller]) > 0)
            {
                Swap(i, smaller);
                Heapify(smaller);
            }
        }
    }
    
    
    
    

Log in to reply
 

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