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

public class Solution {
    int count;
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
	PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
            //PriorityQueue默认是小顶堆，实现大顶堆，需要反转默认排序器
			return o2.compareTo(o1); 
		}
	});

    public void Insert(Integer num) {
    count++;
    if (count & 1) == 0) { // 判断偶数的高效写法
			if (!maxHeap.isEmpty() && num < maxHeap.peek()) {
				maxHeap.offer(num);
				num = maxHeap.poll();
			}
			minHeap.offer(num);
		} else {
			if (!minHeap.isEmpty() && num > minHeap.peek()) {
				minHeap.offer(num);
				num = minHeap.poll();
			}
			maxHeap.offer(num);
		}
    }

    public Double GetMedian() {    
        if(count==0)
            throw new RuntimeException("no available number!");
        double result;
       //总数为奇数时，大顶堆堆顶就是中位数
       if((count&1)==1)
            result=maxHeap.peek();
        else
            result=(minHeap.peek()+maxHeap.peek())/2.0;
        return result;
    }
}

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路

• 先用java集合PriorityQueue来设置一个小顶堆和大顶堆
• 主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
• 小顶堆存较大的数，从小到大的顺序排序*，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。
• ⭐保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值
• ⭐当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
• ⭐当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
• ⭐取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点

理解了上面所述的主体思想，下面举个例子辅助验证一下。

例如，传入的数据为：[5,2,3,4,1,6,7,0,8],那么按照要求，输出是"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

那么整个程序的执行流程应该是（用min表示小顶堆，max表示大顶堆）：

• 5先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[5],max=[无]，avg=[5.00]
• 2先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[5],max=[2],avg=[(5+2)/2]=[3.50]
• 3先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,5],max=[2],avg=[3.00]
• 4先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5],max=[3,2],avg=[(4+3)/2]=[3.50]
• 1先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,4,5],max=[2,1]，avg=[3/00]
• 6先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5,6],max=[3,2,1],avg=[(4+3)/2]=[3.50]
• 7先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1],avg=[4]=[4.00]
• 0先进入小顶堆，然后将小顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1,0],avg=[(4+3)/2]=[3.50]
• 8先进入大顶堆，然后将大顶堆中最小值放入大顶堆中，此时min=[4,5,6,7,8],max=[3,2,1,0],avg=[4.00]

我的答案

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    //小顶堆
    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());
        }
    }
}

struct myTreeNode
{
	int val;
	int count;//以此节点为根的树高
	struct myTreeNode* left;
	struct myTreeNode* right;
	myTreeNode(int v) :
		val(v), 
		count(1), left(NULL), right(NULL) {}

};

myTreeNode *root = NULL;

class Solution
{
public:

	/*计算以节点为根的树的高度
	*/
	int totalCount(myTreeNode* node)
	{
		if (node == NULL)
			return 0;
		else
			return node->count;
	}

	//左左
	void rotateLL(myTreeNode* &t)
	{
		myTreeNode* k = t->left;
		myTreeNode* tm = NULL;
		while (k->right != NULL)
		{
			k->count--;
			tm = k;
			k = k->right;
			
		}
		if (k != t->left)
		{
			k->left = t->left;
			tm->right = NULL;
		}
		t->left = NULL;
		k->right = t;


		t->count = totalCount(t->left) + totalCount(t->right) + 1;
		k->count = totalCount(k->left) + t->count + 1;

		t = k;
	}

	//右右
	void rotateRR(myTreeNode* &t)
	{
		myTreeNode* k = t->right;
		myTreeNode* tm = NULL;
		while (k->left != NULL) {
			k->count--;
			tm = k;
			k = k->left;
			
		}
		if (k != t->right)
		{
			k->right = t->right;
			tm->left = NULL;
		}
			
		t->right = NULL;
		k->left = t;

		t->count = totalCount(t->left) + 1;
		k->count = totalCount(k->right)+ t->count + 1;
		t = k;
	}

	//左右
	void rotateLR(myTreeNode* &t)
	{
		rotateRR(t->left);
		rotateLL(t);
	}

	//右左
	void rotateRL(myTreeNode* &t)
	{
		rotateLL(t->right);
		rotateRR(t);
	}

	//插入
	void insert(myTreeNode* &root, int x)
	{
		if (root == NULL)
		{
			root = new myTreeNode(x);
			return;
		}
		
		if (root->val >= x)
		{
			insert(root->left, x);
			root->count = totalCount(root->left)+ totalCount(root->right) + 1;
			if (2 == totalCount(root->left) - totalCount(root->right))
			{
				if (x < root->left->val)
				{
					rotateLL(root);
				}
				else
				{
					rotateLR(root);
				}
			}
		}
		else
		{
			insert(root->right, x);
			root->count = totalCount(root->left)+ totalCount(root->right) + 1;
			if (2 == totalCount(root->right) - totalCount(root->left))
			{
				if (x > root->right->val)
				{
					rotateRR(root);
				}
				else {
					rotateRL(root);
				}
			}
		}

	}

	void deleteTree(myTreeNode* root)
	{
		if (root == NULL)return;
		deleteTree(root->left);
		deleteTree(root->right);
		delete root;
		root = NULL;
	}
	
	void Insert(int num)
	{
		insert(root, num);
	}

	double GetMedian()
	{
		int lc = totalCount(root->left), rc = totalCount(root->right);
		if ( lc == rc)
			return root->val;
		else
		{
			bool isLeft = lc > rc ;
			myTreeNode* tmp ;
			if (isLeft)
			{
				tmp = root->left;
				while (tmp->right != NULL)
				{
					tmp = tmp->right;
				}
			}
			else {
				tmp = root->right;
				while (tmp->left != NULL)
				{
					tmp = tmp->left;
				}
			}
			return (double)(root->val + tmp->val) / 2.0;
		}
	}

};

#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()

	private int count = 0;
	private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
	private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});

	public void Insert(Integer num) {
		if (count %2 == 0) {//当数据总数为偶数时，新加入的元素，应当进入小根堆
			//（注意不是直接进入小根堆，而是经大根堆筛选后取大根堆中最大元素进入小根堆）
			//1.新加入的元素先入到大根堆，由大根堆筛选出堆中最大的元素
			maxHeap.offer(num);
			int filteredMaxNum = maxHeap.poll();
			//2.筛选后的【大根堆中的最大元素】进入小根堆
			minHeap.offer(filteredMaxNum);
		} else {//当数据总数为奇数时，新加入的元素，应当进入大根堆
			//（注意不是直接进入大根堆，而是经小根堆筛选后取小根堆中最大元素进入大根堆）
			//1.新加入的元素先入到小根堆，由小根堆筛选出堆中最小的元素
			minHeap.offer(num);
			int filteredMinNum = minHeap.poll();
			//2.筛选后的【小根堆中的最小元素】进入大根堆
			maxHeap.offer(filteredMinNum);
		}
		count++;
	}

	public Double GetMedian() {
		if (count %2 == 0) {
			return new Double((minHeap.peek() + maxHeap.peek())) / 2;
		} else {
			return new Double(minHeap.peek());
		}
	}

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);
	}
}

//大家好，我来了！欢迎点赞！
class Solution {
private:
		vector<int> min;
		vector<int> max;
public:
    	void Insert(int num)
    	{
    	   if(((min.size()+max.size())&1)==0)//偶数时 ，放入最小堆 
		   {
		   	  if(max.size()>0 && num<max[0])
		   	  {
		   	  	// push_heap (_First, _Last),要先在容器中加入数据，再调用push_heap ()
		   	  	 max.push_back(num);//先将元素压入容器
		   	  	 push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
				 num=max[0];//取出最大堆的最大值 
				 //pop_heap(_First, _Last)，要先调用pop_heap()再在容器中删除数据
				 pop_heap(max.begin(),max.end(),less<int>());//删除最大堆的最大值 
				 max.pop_back(); //在容器中删除 
			  }
			  min.push_back(num);//压入最小堆 
			  push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
		   }
		   else//奇数时候，放入最大堆
		   {
		   	  if(min.size()>0 && num>min[0])
		   	  {
		   	  	// push_heap (_First, _Last),要先在容器中加入数据，再调用push_heap ()
			     min.push_back(num);//先压入最小堆 
				 push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
				 num=min[0];//得到最小堆的最小值（堆顶） 
				 //pop_heap(_First, _Last)，要先调用pop_heap()再在容器中删除数据
				 pop_heap(min.begin(),min.end(),greater<int>());//删除最小堆的最大值 
				 min.pop_back(); //在容器中删除 
			  }
		   	  max.push_back(num);//压入数字 
		   	  push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
		   }	
		}
		/*获取中位数*/		
		double GetMedian()
		{
			int si敏感词.size()+max.size();
			if(size<=0) //没有元素，抛出异常 
			    return 0;//throw exception("No numbers are available");
			if((size&1)==0)//偶数时，去平均 
			    return ((double)(max[0]+min[0])/2);
			else//奇数，去最小堆，因为最小堆数据保持和最大堆一样多，或者比最大堆多1个 
			    return min[0];
		}
};

python solution

题目有问题，自己要加一个参数，默认少了一个参数！！！

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr = []

    def Insert(self, num):
        self.arr.append(num)
        self.arr.sort()

    def GetMedian(self, ***):
        length = len(self.arr)
        if length % 2 == 1:
            return self.arr[length // 2]
        return (self.arr[length // 2] + self.arr[length // 2 - 1]) / 2.0

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
   

import java.util.*;
// 运行时间：23ms
// 占用内存：9104k
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public void Insert(Integer num) {
        res.add(num);
        Collections.sort(res);
    }

    public Double GetMedian() {
        int n = res.size();
        if (n % 2 == 0) {
            return Double.valueOf((res.get(n / 2) + res.get(n / 2 - 1)) / 2.0);
        } else {
            return Double.valueOf(res.get(n / 2));
        }
    }
}

class Solution {
public:
    void Insert(int num)
    {
        count+=1;
        // 元素个数是偶数时,将小顶堆堆顶放入大顶堆
        if(count%2==0){
            big_heap.push(num);
            small_heap.push(big_heap.top());
            big_heap.pop();
        }
        else{
            small_heap.push(num);
            big_heap.push(small_heap.top());
            small_heap.pop();
        }
    }

    double GetMedian()
    {
        if(count&0x1){
            return big_heap.top();
        }
        else{
            return double((small_heap.top()+big_heap.top())/2.0);
        }
    }
private:
    int count=0;
    priority_queue<int, vector<int>, less<int>> big_heap;        // 左边一个大顶堆
    priority_queue<int, vector<int>, greater<int>> small_heap;   // 右边一个小顶堆
    // 大顶堆所有元素均小于等于小顶堆的所有元素.
};

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 {
	ArrayList<Integer> al = new ArrayList<Integer>();
    public void Insert(Integer num) {
    	al.add(num);
        Collections.sort(al);
    }

    public Double GetMedian() {
        int mid = al.size()/2;
        if((al.size()&1) == 0){
            Integer n1 = al.get(mid);
            Integer n2 = al.get(mid - 1);
            double s = (Double.valueOf(n1 + "") + Double.valueOf(n2 + ""))/2;
            return s;
        }else{
            double s = Double.valueOf(al.get(mid) + "");
            return s;
        }
    }


}