1.问题描述：中位数是有序列表中间的数。如果列表长度是偶数，则中位数是中间两个数字的平均值。例如[2,3,4]的中位数是3[2,3]的中位数是(2+3)/2=2.5设计一个支持以下两种操作的数据结构：voidaddNum(intnum)-将数据流中的整数添加到数据结构中。doublefindMedian()-返回到目前为止所有元素的中值。例子：addNum(1)addNum(2)findMedian()->1.5addNum(3)findMedian()->2二、问题分析1、如果有数据流：[3,1,9,25,12,…]每流入一条数据，先追加到链表尾部，然后排序，然后计算中位数，过程如下：3->[3]中位数：31->[3,1]->[1,3]中位数：(1+3)/2=2.09->[1,3,9]->[1,3,9]中位数：325->[1,3,9,25]->[1,3,9,25]中位数：(3+9)/2=6.012->[1,3,9,25,12]->[1,3,9,12,25]中位数:9最后输出的中位数列表为：[3,2.0,3,6.0,9,...]2.计算过程总结：先排序，再减半如图：可见，求中位数两种情况：列表长度为奇数时：直接取中间数列表长度为偶数时：计算中间两个数的平均值取中值即可。defrunning_medians_naive(iterable):medians=[]values=[]fori,xinenumerate(iterable):values.append(x)values.sort()ifi%2==0:medians.append(values[i//2])else:medians.append((values[i//2]+values[i//2+1])/2)returnmediansrunning_medians_naive([3,1,9,25,12])观察上面算法实现的时间复杂度，可以发现每次都要对list进行排序，比较耗时。4.堆的实现Heap仔细观察计算过程，可以发现取中位数只和链表中心的1-2个值有关，如图：和思路很像heap的Heap，可以把median的左半部分折叠看做是大顶堆max-heap，右半部分看做是小顶堆min-heap，这样堆就可以用了来降低时间复杂度。Python实现由两部分组成：max-heap堆和中值算法。4.1、Max-heap堆类Heap:def__init__(self,key=lambdax:x):self.data=[]self.key=key@staticmethoddef_parent(idx):return(idx-1)//2@staticmethoddef_left(idx):返回idx*2+1@staticmethoddef_right(idx):返回idx*2+2defheapify(self,idx=0):whileidx
