数据流中的中位数【Java版】

【总体思路】设立一个大根堆、一个小根堆，还有一个奇偶标记。
大根堆保存较小的半边，小根堆大的半边；入堆来回倒（以保证中位）、出堆类型转换

import java.util.PriorityQueue;
//Java的PriorityQueue基于堆
//add()添加  poll()弹出顶端元素=>时间都是O(logN)    //peek()查看顶端元素=>时间O(1)
//【poll】比较特别，相当于栈的pop
public class Solution {
    PriorityQueue<Integer> minRootHeap = new PriorityQueue<Integer>();//小根堆
    PriorityQueue<Integer> maxRootHeap = new PriorityQueue<Integer>((x,y) -> y-x);//大根堆：用lambda表达式 调整顺序
    boolean isOdd = false;//可以设置boolean,也可以设置一个Int类型的++i
    //3个全局（类）变量，空间复杂度O(N)

    public void Insert(Integer num) {
        if(isOdd == false){
            minRootHeap.add(num);//插入小根堆  //由于是中位数，所以是对称的，反过来也可
            maxRootHeap.add(minRootHeap.poll());//小根堆最小值，给到大根堆
        }
        else{
            maxRootHeap.add(num);
            minRootHeap.add(maxRootHeap.poll());
        }
        isOdd = !isOdd;
    }//时间O(logN) 空间O(1)

    public Double GetMedian() {//输出的类型是Double
        if(isOdd == true){
            return maxRootHeap.peek() / 1.0;//【强制转换】成Double
        }
        else{
            return (maxRootHeap.peek() + minRootHeap.peek()) / 2.0;
        }
    }//时间O(1) 空间O(1)
}

int 和 Integer 的区别：

1、Integer是int的包装类，int则是java的一种基本数据类型
2、Integer变量必须实例化后才能使用，而int变量不需要
3、Integer实际是对象的引用，当new一个Integer时，实际上是生成一个指针指向此对象；而int则是直接存储数据值
4、Integer的默认值是null，int的默认值是0

深化：

1、由于Integer变量实际上是对一个Integer对象的引用，所以两个通过new生成的Integer变量永远是不相等的（因为new生成的是两个对象，其内存地址不同）。

Integer i = new Integer(100);
Integer j = new Integer(100);
System.out.print(i == j); //false

2、Integer变量和int变量比较时，只要两个变量的值是向等的，则结果为true（因为包装类Integer和基本数据类型int比较时，java会自动拆包装为int，然后进行比较，实际上就变为两个int变量的比较）

Integer i = new Integer(100);
int j = 100；
System.out.print(i == j); //true

3、非new生成的Integer变量和new Integer()生成的变量比较时，结果为false。（因为非new生成的Integer变量指向的是java常量池中的对象，而new Integer()生成的变量指向堆中新建的对象，两者在内存中的地址不同）

Integer i = new Integer(100);
Integer j = 100;
System.out.print(i == j); //false

4、对于两个非new生成的Integer对象，进行比较时，如果两个变量的值在区间 -128 ~ +127之间，则比较结果为true，如果两个变量的值不在此区间，则比较结果为false

Integer i = 100;
Integer j = 100;
System.out.print(i = = j); //true
Integer i = 128;
Integer j = 128;
System.out.print(i = = j); //false