41:データストリームの中位数(剣指offer第2版Python)

1、テーマの説明
データ・ストリームの中位数を取得するにはどうすればいいですか?
データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.Insert()メソッドを用いてデータストリームを読み出し,GetMedian()メソッドを用いて現在の読み出しデータの中位数を取得した.
2、コードの詳細

'''
heapq     
heappush(heap,item) #          
item = heappop(heap) #        
heappushpop() #    ，                 
'''
# -*- coding:utf-8 -*-
from heapq import *
class Solution:
    def __init__(self):
        self.heaps = [], []

    def Insert(self, num):
        #            ，           ，                         
        small, large = self.heaps
        # print('****  ', num, '****')
        # print('small:', small, ',large:', large)
        heappush(small, -heappushpop(large, num))  #  num     large，      large    ，  ，     small
        # print('2small:', small, ',2large:', large)
        if len(large) < len(small):
            heappush(large, -heappop(small))  #   small     ，  ，  large
        # print('3small:', small, ',3large:', large)

    def GetMedian(self, ss=None):
        # write code here
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0


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

****   5 ****
small: [] ,large: []
2small: [-5] ,2large: []
3small: [] ,3large: [5]
5.0
****   2 ****
small: [] ,large: [5]
2small: [-2] ,2large: [5]
3small: [-2] ,3large: [5]
3.5
****   3 ****
small: [-2] ,large: [5]
2small: [-3, -2] ,2large: [5]
3small: [-2] ,3large: [3, 5]
3.0
****   4 ****
small: [-2] ,large: [3, 5]
2small: [-3, -2] ,2large: [4, 5]
3small: [-3, -2] ,3large: [4, 5]
3.5
****   1 ****
small: [-3, -2] ,large: [4, 5]
2small: [-3, -2, -1] ,2large: [4, 5]
3small: [-2, -1] ,3large: [3, 5, 4]
3.0
****   6 ****
small: [-2, -1] ,large: [3, 5, 4]
2small: [-3, -1, -2] ,2large: [4, 5, 6]
3small: [-3, -1, -2] ,3large: [4, 5, 6]
3.5
****   7 ****
small: [-3, -1, -2] ,large: [4, 5, 6]
2small: [-4, -3, -2, -1] ,2large: [5, 7, 6]
3small: [-3, -1, -2] ,3large: [4, 5, 6, 7]
4.0
****   0 ****
small: [-3, -1, -2] ,large: [4, 5, 6, 7]
2small: [-3, -1, -2, 0] ,2large: [4, 5, 6, 7]
3small: [-3, -1, -2, 0] ,3large: [4, 5, 6, 7]
3.5
****   8 ****
small: [-3, -1, -2, 0] ,large: [4, 5, 6, 7]
2small: [-4, -3, -2, 0, -1] ,2large: [5, 7, 6, 8]
3small: [-3, -1, -2, 0] ,3large: [4, 5, 6, 8, 7]
4.0

最大スタックと最小スタックを構築し、それぞれ中位数より小さい数と大きい数を格納します.現在、2つのスタックの総数が偶数の場合、数字を最大スタックに格納し、最大スタックを再配置します.もし最も大きなスタックの数が最小スタックの数より大きい場合、2つのスタックの数を交換し、2つのスタックを再配置します.この場合、2つのスタックの数の総数は奇数で、直接最大スタックの数を出力するのは中位数です.現在の2つのスタックの総数が奇数の場合、数字を最小スタックに格納し、最小スタックを再配置し、最上位のスタックの数が最小スタックの数より大きい場合、2つのスタックの数を交換し、2つのスタックを再配置します.この場合、2つのスタックの数の総数は偶数で、2つのスタックの数を平均すると中位数になります.
https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0.py
3、参考文献
Pythonの山
https://docs.python.org/3.6/library/heapq.html
https://blog.csdn.net/minxihou/article/details/51857518
問題解
https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1?f=discussion
https://github.com/shenweichen/coding_interviews/blob/master/41.%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0/41.%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0.py