63数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值

如果能保证数据容器左边的数据都小于右边的数据，这样即使左右两边没有排序，也可以根据左边最大的数与右边最小的数得到中位数。

用一个最大堆实现左边的数据容器，用一个最小堆实现右边的数据容器。
插入效率o(logn),得到效率o(1)

要保证数据平均分配到2个堆中，因此2个堆中的数据数目之差不能超过1.总数目偶数时插到最小堆中，奇数时插到最大堆中。
读取的时候，奇数时，返回最小堆，偶数时，返回最大最小的平均。

 1 import java.util.Comparator;
 2 import java.util.PriorityQueue;
 3 public class Solution {
 4     private int cnt = 0;
 5     private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
 6     private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15,new Comparator<Integer>(){
 7          @Override
 8         public int compare(Integer o1,Integer o2){
 9             return o2.compareTo(o1);
10         }
11     });
12     
13     public void Insert(Integer num) {
14         if(cnt%2==0){ //insert min
15             maxHeap.offer(num);
16             num = maxHeap.poll();
17             
18             minHeap.offer(num);
19         }
20         else{
21             minHeap.offer(num);
22             num = minHeap.poll();
23             
24             maxHeap.offer(num);
25         }
26         cnt++;
27     }
28     public Double GetMedian() {
29         if(cnt%2==0)
30             return new Double((minHeap.peek()+maxHeap.peek())) /2;
31         else 
32             return new Double(minHeap.peek());
33         
34     }
35 
36 
37 }

c++:20180801

 1 class Solution {
 2     priority_queue<int, vector<int>, less<int> > small;
 3     priority_queue<int,vector<int>,greater<int>> big;
 4 public:
 5     void Insert(int num)
 6     {
 7      if (small.empty()||num<small.top())
 8          small.push(num);
 9      else
10          big.push(num);
11 
12          if (small.size() == big.size()+2) {
13              big.push(small.top());
14              small.pop();
15          }
16          if(small.size()+1 == big.size()){
17              small.push(big.top());
18              big.pop();
19          }
20     }
21 
22     double GetMedian()
23     { 
24         if (big.size() == small.size())
25             return (big.top() + small.top())/2.0;
26         else
27             return small.top();
28     }
29 
30 };

note：

最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者的堆。
最小堆：根结点的键值是所有堆结点键值中最小者的堆。

主要操作（最小堆）

插入

只需要将节点插在二叉树的最后一个叶子结点位置，然后比较它对它父亲节点的大小，如果大则停止；如果小则交换位置，然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))。
一般来说，插入的位置可以不是最后一个叶子节点，可以作为任意中间节点的孩子节点插入，将这个叶子节点变为中间节点后，按上文所说的方法调整节点顺序以保证维持堆特性不变。

删除

要从堆中删除一个节点，用最后一个节点替换掉要刪除的节点，然后调整节点顺序以维持堆特性。