数据流的中位数
中位数是有序列表中间的数，如果列表长度是偶数，中位数则是中间两额数的平均值
解法一
用一个大根堆和一个小根堆，小根堆，存放的是最大的一半数，
大根堆 存放的是最小的一半数。 通过堆顶的元素一定能得中位数。
- 代码实现如下：
class Solution:
def __init__(self):
self.minNums = [] # 小根堆，存放是最大的一半的数
self.maxNums = [] # 大根堆，存放的是最小的一半的数
def maxHeapInsert(self, num):
self.maxNums.append(num)
i = len(self.maxNums) - 1
while i > 0:
if self.maxNums[i] > self.maxNums[(i - 1) // 2]: # 比父节点大就交换
self.swap(self.maxNums, i, (i - 1) // 2)
i = (i - 1) // 2
else:
break
def swap(self, arr, i, j):
"""交换两个变量的值"""
arr[i], arr[j] = arr[j], arr[i]
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: # 左孩子的位置，左孩子不越界
left = 2 * i + 1
if (left + 1 < lens) and self.maxNums[left + 1] > self.maxNums[left]: # 左孩子和右孩子较大值的位置。
left += 1
if self.maxNums[left] > self.maxNums[i]: # 左右孩子中较大的值大于当前值
self.swap(self.maxNums, i, left) # 当前值和两个孩子中较大的值交换
i = left
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]:
self.swap(self.minNums, i, (i - 1) // 2)
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:
left = 2 * i + 1
if (left + 1 < lens) and self.minNums[left] > self.minNums[left + 1]:
left += 1 # 取最小值的下标
if self.minNums[left] < self.minNums[i]: #比当前值小就交换
self.swap(self.minNums,i,left)
i = left
else:
break
return t
def Insert(self, num):
if len(self.minNums) == len(self.maxNums):
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):
if len(self.minNums) == len(self.maxNums):
return (self.maxNums[0] + self.minNums[0]) / 2
else:
return self.minNums[0]
