C# using minimum heap and maximum heap practice in June 2017
July 15, 2019\n295. Find Median from Data Stream\n\nIt is most challenging problem to solve since the optimal solution is to use two data structure, one is mini
July 15, 2019\n295. Find Median from Data Stream\n\nIt is most challenging problem to solve since the optimal solution is to use two data structure, one is minimum heap, and the other one is maximum heap. I was asked to work on the algorithm in phone screen in March 2017. \n\nIt is time for me to review the algorithm again. \n\n**How to design minimum heap and maximum heap using C#?**\n\nUsing C# SortedSet, and also define Comparer. \n\n**One tip to make median calcuation easy**\n\nIt is a good idea to make minimum heap size is bigger than maximum heap size by 1 if total length is is odd. \n\n**Follow up** \nOct. 23, 2020\nI reviewed the code and asked myself why SortedSet is used with int[]. I thought about over 10 minutes. After that, I figured out the following reasons:\n1. SortedSet do not allow duplicated numbers, so in order to store all numbers in the stream, it is better to make all of them unique. Add identity variable with increment one is a good idea.\n2. C# SortedSet class, another example to use the class to define Heap is hard level algorithm. 358 rearrange string k distance apart. \n\n```\npublic class MedianFinder {\n\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        \n    }\n    \n    private int counter = 0;\n\n        private SortedSet<int[]> setLow = new SortedSet<int[]>(\n            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));\n\n        private SortedSet<int[]> setHigh = new SortedSet<int[]>(\n            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));\n            \n    public void AddNum(int num) {\n        var newNum = new int[2] { num, counter++ };\n\n            bool twoTreesSameSize = setLow.Count == setHigh.Count;          \n\n            if (twoTreesSameSize)\n            {\n                if (setLow.Count == 0 || newNum[0] <= setLow.Max[0])\n                {\n                    setLow.Add(newNum);\n                }\n                else\n                {\n                    setHigh.Add(newNum);\n\n                    // move the minimum number from setHigh to setLow. \n                    setLow.Add(setHigh.Min);\n                    setHigh.Remove(setHigh.Min);\n                }\n            }\n            else if (newNum[0] <= setLow.Max[0])\n            {\n                setLow.Add(newNum);\n\n                // move the maximum number from setLow to setHigh\n                setHigh.Add(setLow.Max);\n                setLow.Remove(setLow.Max);\n            }\n            else\n            {\n                setHigh.Add(newNum);\n            }\n    }\n    \n    public double FindMedian() {\n        if (setLow.Count == 0)\n            {\n                return 0;\n            }\n\n            if (setLow.Count == setHigh.Count)\n            {\n                return (setLow.Max[0] + setHigh.Min[0]) / 2d;\n            }\n            else\n            {\n                return setLow.Max[0];\n            }\n    }\n}\n\n/**\n * Your MedianFinder object will be instantiated and called as such:\n * MedianFinder obj = new MedianFinder();\n * obj.AddNum(num);\n * double param_2 = obj.FindMedian();\n */\n ```
[]