数据流中的中位数

#Python版
#该题Python版牛客有问题
#一直提示 def GetMedian(self)函数多给了一个参数 ，然后自己def GetMedian(self,n=None):
#多给它加了一个默认参数，就过了。。。我擦
#思路：两个堆，自己实现，一个最大堆，一个最小堆 

# -*- coding:utf-8 -*-

class Solution:
    def __init__(self):
        self.minNums=[]
        self.maxNums=[]

    def maxHeapInsert(self,num):
        self.maxNums.append(num)
        lens = len(self.maxNums)
        i = lens - 1
        while i > 0:
            if self.maxNums[i] > self.maxNums[(i - 1) / 2]:
                t = self.maxNums[(i - 1) / 2]
                self.maxNums[(i - 1) / 2] = self.maxNums[i]
                self.maxNums[i] = t
                i = (i - 1) / 2
            else:
                break

    def maxHeapPop(self):
        t = self.maxNums[0]
        self.maxNums[0] = self.maxNums[-1]
        self.maxNums.pop()
        lens = len(self.maxNums)
        i = 0
        while 2 * i + 1 < lens:
            nexti = 2 * i + 1
            if (nexti + 1 < lens) and self.maxNums[nexti + 1] > self.maxNums[nexti]:
                nexti += 1
            if self.maxNums[nexti] > self.maxNums[i]:
                tmp = self.maxNums[i]
                self.maxNums[i] = self.maxNums[nexti]
                self.maxNums[nexti] = tmp
                i = nexti
            else:
                break
        return  t

    def minHeapInsert(self,num):
        self.minNums.append(num)
        lens = len(self.minNums)
        i = lens - 1
        while i > 0:
            if self.minNums[i] < self.minNums[(i - 1) / 2]:
                t = self.minNums[(i - 1) / 2]
                self.minNums[(i - 1) / 2] = self.minNums[i]
                self.minNums[i] = t
                i = (i - 1) / 2
            else:
                break

    def minHeapPop(self):
        t = self.minNums[0]
        self.minNums[0] = self.minNums[-1]
        self.minNums.pop()
        lens = len(self.minNums)
        i = 0
        while 2 * i + 1 < lens:
            nexti = 2 * i + 1
            if (nexti + 1 < lens) and self.minNums[nexti + 1] < self.minNums[nexti]:
                nexti += 1
            if self.minNums[nexti] < self.minNums[i]:
                tmp = self.minNums[i]
                self.minNums[i] = self.minNums[nexti]
                self.minNums[nexti] = tmp
                i = nexti
            else:
                break
        return t

    def Insert(self, num):
        if (len(self.minNums)+len(self.maxNums))&1==0:
            if len(self.maxNums)>0 and num < self.maxNums[0]:
                self.maxHeapInsert(num)
                num = self.maxHeapPop()
            self.minHeapInsert(num)
        else:
            if len(self.minNums)>0 and num > self.minNums[0]:
                self.minHeapInsert(num)
                num = self.minHeapPop()
            self.maxHeapInsert(num)

    def GetMedian(self,n=None):
        allLen = len(self.minNums) + len(self.maxNums)
        if allLen ==0:
            return -1
        if allLen &1==1:
            return self.minNums[0]
        else:
            return (self.maxNums[0] + self.minNums[0]+0.0)/2

t = Solution()
t.Insert(5)
print t.GetMedian()
t.Insert(2)
print t.GetMedian()
t.Insert(3)
print t.GetMedian()
t.Insert(4)
print t.GetMedian()
t.Insert(1)
print t.GetMedian()
t.Insert(6)
print t.GetMedian()
t.Insert(7)
print t.GetMedian()
t.Insert(0)
print t.GetMedian()
t.Insert(8)
print t.GetMedian()

public class Solution{
	private Heap maxHeap = new Heap(Heap.isMaxHeap);
	private Heap minHeap = new Heap(Heap.isMinHeap);
	/**
	 * 插入有两种思路：
	 * 1：直接插入大堆中，之后若两堆尺寸之差大于1(也就是2)，则从大堆中弹出堆顶元素并插入到小堆中
	 * 若两队之差不大于1，则直接插入大堆中即可。
	 * 2：奇数个数插入到大堆中，偶数个数插入到小堆中，
	 * 但是 可能会出现当前待插入的数比小堆堆顶元素大，此时需要将元素先插入到小堆，然后将小堆堆顶元素弹出并插入到大堆中
	 * 对于偶数时插入小堆的情况，一样的道理。why?
	 * 因为要保证最大堆的元素要比最小堆的元素都要小。
	 * @param num
	 */
	public void Insert(Integer num) {
		//若总尺寸为偶数，则插入大顶堆中
		if(((maxHeap.si敏感词Heap.size()) & 1) == 0){
			if(minHeap.size() != 0 && num > minHeap.peek()){
				minHeap.add(num);
				maxHeap.add(minHeap.pop());
			}else{
				maxHeap.add(num);
			}
		}else{
			if(maxHeap.size() != 0 && num < maxHeap.peek()){
				maxHeap.add(num);
				minHeap.add(maxHeap.pop());
			}else{
				minHeap.add(num);
			}
		}
	}
	public Double GetMedian() {
		double res = 0.0;
		if(((maxHeap.si敏感词Heap.size()) & 1) == 0){
			res = (maxHeap.peek() + minHeap.peek()) / 2.0;
		}else{
			res = maxHeap.peek();
		}
		return res;
	}
}
//堆类，可直接设置最大堆最小堆
class Heap {
	public List<Integer> list = null;
	public static final boolean isMaxHeap = true;
	public static final boolean isMinHeap = false;
	private boolean flag = true;  //true表示最大堆，false表示最小堆
	public Heap(){
		this.list = new ArrayList<Integer>();
	}
	public Heap(boolean flag){
		this.list = new ArrayList<Integer>();
		this.flag = flag;
	}
	//获取堆大小
	public int size(){
		return this.list.size();
	}
	//获取堆顶元素
	public int peek(){
		if(list.size() == 0) return 0;
		return list.get(0);
	}
	//插入元素，从插入点开始向上调整堆
	public void add(int val){
		this.list.add(val);
		int i = list.size() - 1, index, parent, cur;
		while(i > 0){
			index = (i - 1) / 2;
			parent = list.get(index);
			cur = list.get(i);
			if(flag == true && parent < cur){
				swap(index, i);	
			}else if(flag == false && parent > cur){
				swap(index, i);
			}
			i = index;
		}
	}
	/**
	 * 将堆顶元素取出,并重新调整堆。
	 * 1>取出堆顶元素
	 * 2>将最后一个元素放到堆顶
	 * 3>向下调整堆
	 */
	public int pop(){
		if(list.size() == 0) return -1;
		int res = list.get(0);
		list.set(0,list.get(list.size() - 1));
		list.remove(list.size()-1);
		int len = list.size() - 1 , i = 0;
		int left , right;
		while(i < len){
			left = (i << 1) + 1;
			right= (i << 1) + 2;
			int maxIndex = i;
			if(flag == true){
				if(left < len && list.get(left) > list.get(maxIndex)) maxIndex = left;
				if(right< len && list.get(right)> list.get(maxIndex)) maxIndex = right;
			}else{
				if(left < len && list.get(left) < list.get(maxIndex)) maxIndex = left;
				if(right< len && list.get(right)< list.get(maxIndex)) maxIndex = right;
			}
			if(maxIndex != i){
				swap(maxIndex,i);
				i = maxIndex;
			}else break;
		}
		return res;
	}
	//交换list中两个位置的元素
	public void swap(int i, int j){
		int temp = list.get(i);
		list.set(i, list.get(j));
		list.set(j,temp);
	}
}

PYTHON

参考：https://leetcode.com/problems/find-median-from-data-stream/discuss/74062/Short-simple-JavaC++Python-O(log-n)-+-O(1)
使用两个堆：

• 大根堆：large保存大的半数的数据
• 小根堆：small保存小的半数的数据
  获取中位数的时间复杂度为O（1），插入一个数据的时间复杂度为O（log(n)）

技巧：

1. 构造小根堆时，对数组元素取负值来构造
2. heappush(heap,data),将deat放入大根堆中
3. heapposh(heap),弹出heap中的最小值
4. heappushpop(heap,data),将data放入大根堆中，再弹出堆heap的最小值

   # -*- coding:utf-8 -*-
   from heapq import *
   class Solution:
    def __init__(self):
        self.heaps = [], []
    def Insert(self, num):
        # write code here
        small, large = self.heaps
        heappush(small, -heappushpop(large, num))#将num放入大根堆，并弹出大根堆的最小值，取反，放入大根堆small
        if len(large) < len(small):
            heappush(large, -heappop(small)) #弹出small中最小的值，取反，即最大的值，放入large
    def GetMedian(self,ss):
        # write code here
        small,large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) /2.0
   

mark版的详细解释（c++）

class Solution {
public:
    void Insert(int num)
    {
        if(left.empty() || num <= left.top()){
            left.push(num);
        }else{
            right.push(num);
        }
        // 左边大顶堆的大小最多可以比右边小顶堆大1（奇数次输入）
        if(left.size() == right.size() + 2){ 
            right.push(left.top());
            left.pop();
        }
        // 因为最后返回的只有可能是左边大顶堆的堆顶，所以右边小顶堆的大小不能比左边小顶堆大
        if(left.size() + 1 == right.size()){
            left.push(right.top());
            right.pop();
        }
    }
    double GetMedian()
    {
        return left.size() == right.size() ? (left.top() + right.top())/2\. : left.top();
    }
private:
    // 右边小顶堆的元素都大于左边大顶堆的元素，并且左边元素的个数，要么与右边相等（偶数次输入），要么比右边大1（奇数次输入）
    priority_queue, less > left; // 大顶堆
    priority_queue, greater > right; // 小顶堆
};

最大堆和最小堆的底层实现

class Solution {
private:
    vector<int> max_heap;
    vector<int> min_heap;

    void adjust_heap(vector<int> &nums, int lo, int hi, bool is_max) {
        for (int cur = lo, next = cur * 2 + 1; next <= hi; cur = next, next = cur * 2 + 1) {
            if (is_max) {
                if (next < hi && nums[next + 1] > nums[next]) {
                    ++next;
                }
                if (nums[next] > nums[cur]) {
                    swap(nums[next], nums[cur]);
                } else {
                    break;
                }
            } else {
                if (next < hi && nums[next + 1] < nums[next]) {
                    ++next;
                }
                if (nums[next] < nums[cur]) {
                    swap(nums[next], nums[cur]);
                } else {
                    break;
                }
            }
        }
    }

    void build_heap(vector<int> &heap, bool is_max) {
        int n = heap.size();
        for (int i = n / 2 - 1; i >= 0; --i) {
            adjust_heap(heap, i, n - 1, is_max);
        }
    }

    int pop(vector<int> &heap, bool is_max) {
        int ret = heap[0];
        heap.erase(heap.begin());
        build_heap(heap, is_max);
        return ret;
    }

    void push(vector<int> &heap, int num, bool is_max) {
        heap.emplace_back(num);
        build_heap(heap, is_max);
    }

public:
    void Insert(int num) {
        if (min_heap.empty() || num > min_heap[0]) {
            push(min_heap, num, false);
        } else {
            push(max_heap, num, true);
        }

        if (min_heap.size() == max_heap.size() + 2) {
            push(max_heap, pop(min_heap, false), true);
        }

        if (min_heap.size() + 1 == max_heap.size()) {
            push(min_heap, pop(max_heap, true), false);
        }
    }

    double GetMedian() {
        return min_heap.size() == max_heap.si***_heap[0] + max_heap[0]) / 2. : min_heap[0];
    }

};

    private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
    private PriorityQueue<Integer> max = new PriorityQueue<Integer>(15,new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    private int count = 0;
    public void Insert(Integer num) {
        count++;
        if (count % 2 == 1){
            max.offer(num);//先从大顶堆过滤一遍
            min.offer(max.poll());
        }else {
            min.offer(num);//先从小顶堆过滤一遍
            max.offer(min.poll());
        }
    }
    public Double GetMedian() {
        if (count % 2 == 0)     return (min.peek() + max.peek())/2.0;
        else                    return (double)min.peek();
    }

//    LinkedList<Integer> data = new LinkedList<Integer>();
//    public void Insert(Integer num) {
//        for (int i = data.size() - 1; i >= 0 ; i--) {
//            if (num >= data.get(i)){
//                data.add(i+1,num);
//                return;
//            }
//        }
//        data.addFirst(num);
//    }
//
//    public Double GetMedian() {
//        int size = data.size();
//        if (size% 2 == 1)   return (double)data.get(size/2);
//        else                return (data.get(size/2) + data.get(size/2 - 1))/2.0;
//    }

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution {
    // smaller堆用于存放相对较小的一半数字，larger堆用于存放相对较大的一半数字
    // 由于默认排序堆顶是最小值，而对于smaller的一半我们更关注最大值，因此使用reverseOrder()来初始化
    private PriorityQueue<Integer> smaller = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> larger = new PriorityQueue<>();

    public void Insert(Integer num) {
        // 首次将数字存入smaller，然后在将smaller中堆顶的（较小一半数字的最大值）存入larger
        smaller.add(num);
        larger.add(smaller.poll());
        // 为了保证larger内的数量<=smaller内的数量，进行两个堆大小的比较，并进行转移
        // 此规则下，如果两个堆数量相等，则中位数为两个堆顶数字的平均值；若不相等则为smaller的堆顶数字
        // 也可以使larger存储更多数字，则不相等时，中位数为larger的堆顶数字
        if (larger.size() > smaller.size()) {
            smaller.add(larger.poll());
        }
    }

    public Double GetMedian() {
        // 如前所述，两者大小相等，则求平均
        if (smaller.size() == larger.size()) {
            return ((double)smaller.peek() + (double)larger.peek()) / 2;
        } else { // 否则中位数为smaller的堆顶数字
            return (double)smaller.peek();
        }
    }

}

//看大家都用堆，那我来个树，插入和取中值复杂度都是lgn
public class Solution {
    private TreeNode root;
    public void Insert(Integer num) {
        root = Insert(root, num);
    }
    private TreeNode Insert(TreeNode node, Integer num){
        if(node == null)
            return new TreeNode(num, 1);
        node.size++;
        if(num <= node.val)
            node.left = Insert(node.left, num);
        else
            node.right = Insert(node.right, num);
        return node;
    }
    public Double GetMedian() {
        if(root == null)
            return null;
        if((root.size & 1) == 0)
            return (double)(getKth(root, root.size/2) + getKth(root, root.size/2 + 1))/2;
        else
            return (double)getKth(root, (root.size + 1)/2);
    }
    private int getKth(TreeNode node, int k){
        int size = node.left == null ? 0 : node.left.size;
        if(k <= size)
            return getKth(node.left, k);
        else if(k == size + 1)
            return node.val;
        else
            return getKth(node.right, k-size-1);
    }
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        int size = 0;//该字段的含义是以该节点为子树根的节点总个数
        public TreeNode(int val, int size) {
            this.val = val;
            this.size = size;
        }
    }
}

import java.util.*;

public class Solution {
    // 代表排序后的左半部分
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    // 代表排序后的右半部分
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    // 时间复杂度O(logn)
    public void Insert(Integer num) {
        // 平均分配，元素个数为奇数时插入到maxHeap，为偶数时插入到minHeap
        if ((minHeap.size() + maxHeap.size()) % 2 == 1) {
            // 若num完全小于minHeap的所有元素，直接将num插入maxHeap即可
            // 若num大于minHeap中的一些元素，则将num插入minHeap, 然后移除minHeap的最小值，将其插入maxHeap
            if (!minHeap.isEmpty() && num > minHeap.element()) {
                minHeap.add(num);
                num = minHeap.remove();
            }
            maxHeap.add(num);
        } else {
            // 若num完全大于maxHeap的所有元素，直接将num插入minHeap即可
            // 若num小于maxHeap中的一些元素，则将num插入maxHeap，然后移除maxHeap的最大值，将其插入minHeap
            if (!maxHeap.isEmpty() && num < maxHeap.element()) {
                maxHeap.add(num);
                num = maxHeap.remove();
            }
            minHeap.add(num);
        }
    }

    // 时间复杂度O(1)
    public Double GetMedian() {
        int size = maxHeap.size() + minHeap.size();
        if (size % 2 == 1) {
            return minHeap.element() * 1.0;
        } else {
            return (maxHeap.element() + minHeap.element()) / 2.0;
        }
    }

}

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
 //	初始化一个大根堆，存中位数左边的数据，一个小根堆，存中位数右边的数据
//	动态维护两个数据结构的大小，即最多只相差一个
//	因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
//	小顶堆存较大的数，从小到大的顺序排序*，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。
//	保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值
//	当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
//	当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
//	取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点
	// 小顶堆
	private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

	// 大顶堆
	private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});

	// 记录偶数个还是奇数个
	int count = 0;

	// 每次插入小顶堆的是当前大顶堆中最大的数
	// 每次插入大顶堆的是当前小顶堆中最小的数
	// 这样保证小顶堆中的数永远大于等于大顶堆中的数
	// 中位数就可以方便地从两者的根结点中获取了
	public void Insert(Integer num) {
		// 个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
		if (count % 2 == 0) {
			maxHeap.offer(num);
			int max = maxHeap.poll();
			minHeap.offer(max);
		} else {
			// 个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
			minHeap.offer(num);
			int min = minHeap.poll();
			maxHeap.offer(min);
		}
		count++;
	}

	public Double GetMedian() {
		// 当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
		if (count % 2 == 0) {
			return new Double(minHeap.peek() + maxHeap.peek()) / 2;
		} else {
			// 当前为奇数个，则直接从小顶堆中取元素即可
			return new Double(minHeap.peek());
		}
	}


}

import java.util.Arrays;
public class Solution {
	static int[] seq = new int[0];
	public static void Insert(Integer num) {
		//    	int stop = list.size(), start = 0;
		int stop = seq.length-1, start = 0;
		if(seq.length == 0){
			seq = Arrays.copyOf(seq, 1);
			seq[0] = num;
		}else{
			while(stop >= start){
				int mid = (start+stop) >>> 1;
				if(seq[mid] < num){
					start = mid + 1;
				}else if(seq[mid] > num){
					stop = mid - 1;
				}else{ // key == mid
					seq = Arrays.copyOf(seq, seq.length+1);
					for(int i = seq.length-1;i > mid;i--){
						seq[i] = seq[i-1];
					}
					seq[mid] = num;
					break;
				}
			}
			if(start > seq.length-1){//num bigger than last key
				seq = Arrays.copyOf(seq, seq.length+1);
				seq[start] = num;
			}else if(stop < 0){ //num less than first key
				seq = Arrays.copyOf(seq, seq.length+1);
				for(int i = seq.length-1; i >0;i--){
					seq[i] = seq[i-1];
				}
				seq[start] = num;
			}else{ // num in between the seq
				seq = Arrays.copyOf(seq, seq.length+1);
				for(int i = seq.length-1; i > start;i--){
					seq[i] = seq[i-1];
				}
				seq[start] = num;
			}
		}
	}
	public static Double GetMedian() {
		int len = seq.length;
		if(len %2 ==0){
			return (seq[len/2]+seq[len/2-1])/2.0;
		}
		return seq[len/2]*1.0;
	}

}

class Solution {
private:
    vector<int> big_part;
    vector<int> small_part;
public:
    void Insert(int num)
    {
        if (small_part.empty()) {
            small_part.push_back(num);
        }
        else {
            if (small_part.size() == big_part.size()) {
                if (num <= big_part.front()) {
                    small_part.push_back(num);
                    push_heap(small_part.begin(), small_part.end());
                }
                else {
                    pop_heap(big_part.begin(), big_part.end(), greater<int>());
                    small_part.push_back(big_part.back());
                    big_part.back() = num;
                    push_heap(small_part.begin(), small_part.end());
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
            }
            else {
                if (num >= small_part.front()) {
                    big_part.push_back(num);
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
                else {
                    pop_heap(small_part.begin(), small_part.end());
                    big_part.push_back(small_part.back());
                    small_part.back() = num;
                    push_heap(small_part.begin(), small_part.end());
                    push_heap(big_part.begin(), big_part.end(), greater<int>());
                }
            }
        }
    }

    double GetMedian()
    { 
        if (small_part.size() == big_part.size()) {
            return static_cast<double>(small_part.front() + big_part.front()) / 2;
        }
        else {
            return small_part.front();
        }
    }

};

class Solution {
public:
	void Insert(int num) {
		data.push_back(num);
		std::sort(data.begin(), data.end());
	}

	double GetMedian() {
		unsigned int size = data.size();
		if (size & 1) {
			return data[size >> 1];
		} else {
			int left = data[(size >> 1) - 1];
			int right = data[size >> 1];
			return (static_cast<double>(left) + right) / 2;
		}
	}
private:
	vector<int> data;
};

python2.7 时间：30ms 内存：5760k
class Solution:
    def __init__(self):
        self.arr = []
    def Insert(self, num):
        if len(self.arr)==0:
            self.arr.append(num)
        else:
            i = len(self.arr)-1
            while num > self.arr[i]:
                i -= 1
            self.arr.insert(i+1,num)
    def GetMedian(self, no):
        # write code here
        length = len(self.arr)
        if length %2 ==1 :
            return self.arr[length//2]
        else:
            return (self.arr[length//2] + self.arr[length//2-1])/2

前后段使用的都是小根堆，只是前半段的小根堆加入的是取负号的元素值，从前半段小根堆pop出最小值（负值），取上负号就是最大值了

from heapq import *  # 导入小根堆
class Solution:
    pre = []  # 前半部分
    after = []  # 后半部分
    def Insert(self, num):
        pre = self.pre
        after = self.after
        # 往后半部分添加元素
        # 每次从后半部分pop出一个最小值加入前半部分
        # 相当于后半部分长度不变，前半部分长度+1
        heappush(pre, -heappushpop(after, num))
        # 维持前后段元素个数相差不超过1
        if len(after) < len(pre):
            # 从前半部分pop出一个最小值（这个值是负数，添负号后就是最大值）
            # 将添负号后的值（前半部分最大值）加入到后半部分
            heappush(after, -heappop(pre)) 
    def GetMedian(self):
        pre = self.pre
        after = self.after
        # 后半部分比前半部分多一位，中位数 = 后半部分[0]
        if len(after) > len(pre):
            return after[0]
        else:
            # 中位数 = （后半部分最小值 + 前半部分最大值 ）/ 2 
            # 因为前部分小根堆里的元素是负值
            # pop出最小的负值取负号就能拿到前半部分的最大值
            return (after[0] - pre[0]) / 2 

import java.util.*;
public class Solution {

    //堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
    
    public void Insert(Integer num) {
        if(maxHeap.isEmpty() || num < maxHeap.peek())
            maxHeap.add(num);
        else
            minHeap.add(num);
        
        modifyTwoHeaps();
    }

    public Double GetMedian() {
        if(maxHeap.size() == minHeap.size())
            return ( maxHeap.peek() + minHeap.peek() ) / 2.0;
        else
            return maxHeap.size() > minHeap.size() ? (double)maxHeap.peek() : (double)minHeap.peek();
    }
    
    private void modifyTwoHeaps(){
        if(maxHeap.size() == minHeap.size() + 2)
            minHeap.add(maxHeap.poll());
        if(minHeap.size() == maxHeap.size() + 2)
            maxHeap.add(minHeap.poll());
    }

}

采用插入排序思想即可解决问题。

import java.util.*;
public class Solution {
    ArrayList list = new ArrayList();
    public void Insert(Integer num) {
      int index = list.size();
        for(int i=0;i<index;++i){
            if(list.get(i)>num){
                index = i;    
            }
        }
        list.add(index,num);
    }
    public Double GetMedian() {
        int len = list.size();
        if(len==0)return null;
        int i = len/2;
        if(len%2==0)return (double )(list.get(i)+list.get(i-1))/2;
        else return (double)list.get(i);
    }
}

  // 从小到大
    PriorityQueue<Integer> max = new PriorityQueue<>();
    // 从大到小
    PriorityQueue<Integer> min = new PriorityQueue<>( (x, y) -> y-x);

    public void Insert(Integer num) {
        if(max.size() == min.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public Double GetMedian() {
          return (Double)( max.size() == min.size() ? (max.peek() + min.peek()) / 2.0 : max.peek());
    }