מריה בוטוסוב

יש למצוא חציון של זרם של מספרים

public class MedianFinder {
 
    double median = 0;
    Heap lowers;
    Heap greaters;
    /** initialize your data structure here. */
    public MedianFinder() {
        this.lowers = new Heap(MAX_HEAP_FUNC);
        this.greaters = new Heap(MIN_HEAP_FUNC);
    }
    
    public void AddNum(int num) {
        if(lowers.Length == 0 || num < lowers.Peek())
            this.lowers.Insert(num);
        else
            this.greaters.Insert(num);
        this.rebalanceHeaps();
        this.updateMedian();
    }
    
     private void rebalanceHeaps() {
        if(lowers.Length - greaters.Length == 2)
            this.greaters.Insert(this.lowers.Remove());
         else if (greaters.Length - lowers.Length == 2)
             this.lowers.Insert(this.greaters.Remove());
     }
    
    
    private void updateMedian() {
        if(lowers.Length == greaters.Length)
            median = ((double) lowers.Peek() + (double) greaters.Peek()) / 2;
        else if(lowers.Length > greaters.Length)
            median = lowers.Peek();
        else 
            median = greaters.Peek();    
    }
    
    
    
    public double FindMedian() {
        return median;
    }
            
    private bool MAX_HEAP_FUNC(int a, int b) {
        return a > b;    
    }
    
    private bool MIN_HEAP_FUNC(int a, int b) {
        return a < b;    
    }
 
}
 
 
 public class Heap {
     private List<int> heap = new List<int>();
     public Func<int, int, bool> ComparisonFunc;
     public int Length;
     
     public Heap(Func<int, int, bool> func) {
         this.ComparisonFunc = func;
         //this.heap = BuildHeap(array);
         this.Length = this.heap.Count;
     }
     
     public int Peek() {
         return heap[0];         
     }
     
     public int Remove() {
         swap(0, heap.Count - 1);
         int val = heap[heap.Count - 1];
         this.heap.RemoveAt(heap.Count - 1);
         this.Length--;
         this.SiftDown(0, heap.Count - 1);
         return val;
     }
     
     public void Insert(int val) {
         this.heap.Add(val);
         this.Length++;
         this.SiftUp(heap.Count - 1);
     }
     
     private List<int> BuildHeap(List<int> array) {
         int firstParentIdx = (array.Count - 2) / 2; //LAST Parent NODE as start point
         for(int i = firstParentIdx; i >= 0; i--) {
             this.SiftDown(i, array.Count - 1);
         }
         return array;
     }
     
     private void SiftDown(int currentIdx, int endIdx) {
         int childOneIdx  = currentIdx * 2 + 1;
         while(childOneIdx <= endIdx) {
             int childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
             int idxToSwap;
             if(childTwoIdx != -1 && ComparisonFunc(heap[childTwoIdx], heap[childOneIdx]))
                idxToSwap = childTwoIdx;
             else
                idxToSwap = childOneIdx;
             if(ComparisonFunc(heap[idxToSwap], heap[currentIdx])) {
                 swap(currentIdx, idxToSwap);
                 currentIdx = idxToSwap;
                 childOneIdx = currentIdx * 2 + 1;
             }
             else return; //nothing to siftDown anymore
         }
     }
     
     private void SiftUp(int currentIdx) {
         int parentIdx = (currentIdx - 1) / 2;
         while(currentIdx > 0) {
             if(ComparisonFunc(heap[currentIdx], heap[parentIdx])) {
                 swap(currentIdx, parentIdx);
                 currentIdx = parentIdx;
                 parentIdx = (currentIdx - 1) / 2;
             }
         }
     }
     
     private void swap(int i, int j) {
         int temp = heap[i];
         heap[i] = heap[j];
         heap[j] = temp;
     }
 }

public class MedianFinder {
    private readonly List<int> store = new List<int>();
 
    public void AddNum(int num)
    {
        int index = store.BinarySearch(num);            
        index = index >= 0 ? index : ~index;
        store.Insert(index, num);
    }
 
    public double FindMedian()
    {
        int count = store.Count;
        return count % 2 != 0 ? store[count / 2] : ((double)(store[count / 2 - 1] + store[count / 2])) / 2;
    }
}