295. Find Median from Data Stream

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if (l_.empty() || num < l_.top()) {
            l_.push(num);
        } else {
            r_.push(num);
        }
        
        if (r_.size() > l_.size()) {
            l_.push(r_.top());
            r_.pop();
        } 
        if (l_.size() - r_.size() == 2) {
            r_.push(l_.top());
            l_.pop();
        }
    }
    
    double findMedian() {
        if (l_.size() > r_.size()) return static_cast<double>(l_.top());
        else return static_cast<double>(l_.top() + r_.top()) / 2;
    }
    
private:
    priority_queue<int, vector<int>, less<int>> l_;
    priority_queue<int, vector<int>, greater<int>> r_;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

// Author: Huahua
// Running time: 172 ms
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}
    
    // O(logn)
    void addNum(int num) {
        if (m_.empty()) {
            l_ = r_ = m_.insert(num);
            return;
        }
        
        m_.insert(num);
        const size_t n = m_.size();    
        
        if (n & 1) {
            // odd number
            if (num >= *r_) {         
                l_ = r_;
            } else {
                // num < *r_, l_ could be invalidated
                l_ = --r_;
            }
        } else {
            if (num >= *r_)
                ++r_;
            else
                --l_;
        }
    }
    // O(1)
    double findMedian() {
        return (static_cast<double>(*l_) + *r_) / 2;
    }
private:
    multiset<int> m_;
    multiset<int>::const_iterator l_;  // current left median
    multiset<int>::const_iterator r_;  // current right median
};

class MedianFinder {
    private Node root;
    private Node medianLeft;
    private Node medianRight;
    private int size;

    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        if (root == null) {
            root = new Node(num);
            medianLeft = root;
            medianRight = root;
        } else {
            root.addNode(num);
            if (size % 2 == 0) {
                if (num < medianLeft.data) {
                    medianRight = medianLeft;
                } else if (medianLeft.data <= num && num < medianRight.data) {
                    medianLeft = medianLeft.successor();
                    medianRight = medianRight.predecessor();
                } else if (num >= medianRight.data) {
                    medianLeft = medianRight;
                }
            } else {
                if (num < medianLeft.data) {
                    medianLeft = medianLeft.predecessor();
                } else {
                    medianRight = medianRight.successor();
                }
            }
        }
        size++;
    }
    
    public double findMedian() {
        return (medianLeft.data + medianRight.data) / 2.0;
    }
    
    class Node {
        private Node parent;
        private Node left;
        private Node right;
        private int data;
        
        public Node(int data) {
            this.data = data;
        }
        
        public void addNode(int data) {
            if (data >= this.data) {
                if (right == null) {
                    right = new Node(data);
                    right.parent = this;
                } else {
                    right.addNode(data);
                }
            } else {
                if (left == null) {
                    left = new Node(data);
                    left.parent = this;
                } else {
                    left.addNode(data);
                }
            }
        }
        
        public Node predecessor() {
            if (left != null) {
                return left.rightMost();
            }
            
            Node predecessor = parent;
            Node child = this;
            
            while (predecessor != null && child != predecessor.right) {
                child = predecessor;
                predecessor = predecessor.parent;
            }
            
            return predecessor;
        }
        
        public Node successor() {
            if (right != null) {
                return right.leftMost();
            }
            
            Node successor = parent;
            Node child = this;
             while (successor != null && child != successor.left) {
                 child = successor;
                 successor = successor.parent;
             }
            
            return successor;
        }
        
        public Node leftMost() {
            if (left == null) return this;
            return left.leftMost();
        }
        
        public Node rightMost() {
            if (right == null) return this;
            return right.rightMost();
        }
    };
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */