[295]find median from data strea

leetcode

two heap

use two heap is quite straight forward.

import java.util.Comparator;
import java.util.PriorityQueue;

public class MedianFinder {
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    MedianFinder(){
        left = new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        right = new PriorityQueue<>();
    }


    // Adds a number into the data structure.
    public void addNum(int num) {
        if(left.size() == 0)left.add(num);

        else{
            if(num < left.peek()){
                left.add(num);
            } else {
                right.add(num);
            }
        }
        if(right.size() > left.size())left.offer(right.poll());

        if(left.size() > right.size() + 1){
            right.offer(left.poll());
        }

    }

    // Returns the median of current data stream
    public double findMedian() {
        if(left.size() == right.size()){
            return (left.peek() + right.peek()) / 2.0;
        }
        else return left.peek();

    }


}

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

use binary tree

Use the binary search tree to maintain the structure.
Each add operation, insert the number into BST.

So "find median" is the same task as the "select" operation, which has something to do with the rank.

you can see the algo slides from Princeton for a clear view:
princeton slides

The idea to implement that is to maintain a variable for each node, to record the size of left child.

public class MedianFinder {
    Tree tree;

    class Tree{
        TreeNode root;
        int total;

        public void display(TreeNode root){
            if(root == null) System.out.print("# ");
            else {
                System.out.print(root.val + " " );
                display(root.left);
                display(root.right);
            }
        }

        public void insert(int num){
            total++;
            root = insertHelper(root,num);
        }

        public TreeNode insertHelper(TreeNode root,int num){

            if(root == null) return new TreeNode(num);



            if(root.val <= num){

                root.right = insertHelper(root.right,num);
            } else {
                root.count++;
                root.left = insertHelper(root.left,num);

            }

            return root;


        }
    }

    class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        int count;

        TreeNode(int val){
            this.val = val;
        }

    }

    MedianFinder(){
        tree = new Tree();

    }

    // Adds a number into the data structure.
    public void addNum(int num) {
        this.tree.insert(num);
    }

    // Returns the median of current data stream
    public double findMedian() {


        if(tree.total % 2 == 0){
            int a = findRank(tree.root,tree.total / 2 - 1).val;
            int b = findRank(tree.root,tree.total / 2).val;
            return (a + b) / 2.0;

        } else {
            return findRank(tree.root, tree.total / 2).val;

        }




    }

    public TreeNode findRank(TreeNode root, int k){
        //System.out.println(k);
        if(root == null)return null;

        if(root.count == k)return root;

        if(root.count < k){
            return findRank(root.right,k - root.count - 1);
        } else {
            return findRank(root.left,k);
        }


    }

    public static void main(String[] args){
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        mf.addNum(2);
        mf.addNum(3);
        mf.addNum(4);
        mf.addNum(0);
        mf.addNum(10);
        mf.addNum(12);
        //mf.tree.display(mf.tree.root);

        System.out.println(mf.findMedian());
    }
}

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();