LeetCode-Python-295. データ・ストリームの中央値

中位数は、シーケンステーブルの中央にある数です.リスト長が偶数の場合、中央値は中間の2つの数の平均です.
たとえば、
[2,3,4]の中位数は3
[2,3]の中央値は(2+3)/2=2.5
次の2つの操作をサポートするデータ構造を設計します.

void addNum(int num)-データ・ストリームからデータ構造に整数を追加します.

double findMedian()-現在のすべての要素の中央値を返します.

例:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

考え方:
大きなスタックと小さなスタックでデータを維持します
数えるたびに、まず小さな天井に捨てて、それから小さな天井の天井を大きな天井に捨てて、
2つのスタックをsize差が最大1になるように調整します.
このような利点は、小さなトップスタックはデータストリームの前半の大きな数であり、大きなトップスタックはデータストリームの後半の大きな数であり、
しかも小天井のsizeは一定>=大天井のsizeで、
小頂堆の堆頂Mは小頂堆の中で最小の数であり、大頂堆の堆頂Nは大頂堆の中で最大の数であり、
2つのスタックのsizeが同じである場合、中位数はreturn(M+N)/2.0である.
それ以外の場合、return M/1.0です.
注意pythonには大きなスタックがないので、大きなスタックに入れた数に-1を掛け、取り出すときも*-1を覚えておきましょう.

from heapq import *
class MedianFinder(object):
#      ，     ，     ，                ， 
#            （   size  ），                 2
#          ，  size         
#            ，              ，
#      ，  size     1
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max_h = list()
        self.min_h = list()
        heapify(self.max_h)
        heapify(self.min_h)
        

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        heappush(self.min_h, num)
        heappush(self.max_h, -heappop(self.min_h))
        if len(self.max_h) > len(self.min_h):
            heappush(self.min_h, -heappop(self.max_h))

    def findMedian(self):
        """
        :rtype: float
        """
        max_len = len(self.max_h)
        min_len = len(self.min_h)
        if max_len == min_len: #        
            return (self.min_h[0] + -self.max_h[0]) / 2.
        else:#    size    >=     size，            
            return self.min_h[0] / 1.
            
        


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()