为什么要把这两个算法放在一起呢，这两个算法都用了空间换时间的方法来维护对应的值。
双堆栈维护max或者min的思路是：
当加入元素的时候，首先一个堆栈来存放新加入的元素。
和第二个元素的尾部比较（也就是它的最大值，这里需要考虑刚开始的时候需要直接存放上去），如果加入元素比最大值大，我们把元素放入第二个堆栈中。
如果比最大元素小我们就把最大值再次压入堆栈。
在弹出元素的时候，我们一次弹出第一个堆栈和第二个堆栈的末尾元素即可
代码如下：
classStack(object):
def __init__(self):
self.data=[]
self.max=[]
def push(self, elem):
self.data.append(elem)
if not self.max:
self.max.append(elem)
elif self.max[-1] < elem:
self.max.append(elem)
else:
self.max.append(self.max[-1])
def pop(self):
self.data.pop()
self.max.pop()
def get_max(self):
return self.max[-1]
#123212
#123333
self.data.pop()
self.max.pop()
defget_max(self):
returnself.max[-1]
stack=Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(2)
stack.push(1)
stack.push(2)
stack.pop()
stack.pop()
stack.pop()
接下来是双堆维护中位数了，重要思路是：
- 构造两个堆， 一个大顶堆， 一个小顶堆。
- 把第一个元素拿出来设置为中位数，
- 再拿出第二个元素，如果比中位数大，则放在小顶堆中，如果比中位数小，则放在大顶堆中。
- 左右两个堆的大小不能大于1，当出现大于1的情况时，我们需要动态改变堆的大小， 请看5
- 先把中位数放入数量小的堆中，再pop出大堆中的数，设置为中位数。
class MaxHeap(object):
def __init__(self):
self.heap = []
self.length = 0
def add(self, elem):
#interface add new data
if not self.heap:
self.heap.append(elem)
self.length += 1
else:
self.heap.append(elem)
self.length += 1
position = self.length - 1
self._adjust(elem, position)
def _adjust(self, elem, position):
#adjust heap when add new data
parent = (position - 1) // 2
if position == 0:
return
elif elem > self.heap[parent]:
self.heap[position], self.heap[parent] = self.heap[parent], self.heap[position]
self._adjust(elem, parent)
else:
return
def pop(self):
self.length -= 1
#pop the max data
return self.heap.pop(0)
class MinHeap(object):
def __init__(self):
self.heap = []
self.length = 0
def add(self, elem):
if not self.heap:
self.heap.append(elem)
self.length += 1
else:
self.heap.append(elem)
self.length += 1
position = self.length - 1
self._adjust(elem, position)
def _adjust(self, elem, position):
# adjust heap when add new data
parent = (position - 1) // 2
if position == 0:
return
elif elem < self.heap[parent]:
self.heap[position], self.heap[parent] = self.heap[parent], self.heap[position]
self._adjust(elem, parent)
else:
return
def pop(self):
self.length -= 1
# pop the min data
return self.heap.pop(0)
def finder(mlist):
#维护中位数
maxHeap = MaxHeap()
minHeap = MinHeap()
#保存中位数
middle = mlist[0]
target_length = len(mlist)
odd = 1
if not target_length & 1:
odd = 0
for x in mlist[1:]:
#判断大小两个堆维护的数的差
if x > middle:
minHeap.add(x)
elif x <= middle:
maxHeap.add(x)
#如果差大于1，则需要调整
if maxHeap.length - minHeap.length > 1:
#如果大顶堆存放数量大于小顶堆存放数量
minHeap.add(middle)
#获得大顶堆中最大的数
middle = maxHeap.pop()
if minHeap.length - maxHeap.length > 1:
maxHeap.add(middle)
middle = minHeap.pop()
if odd:
print(maxHeap.heap)
print(minHeap.heap)
return middle
elif maxHeap.length < minHeap.length:
return middle, minHeap.pop()
elif maxHeap.length > minHeap.length:
return middle, maxHeap.pop()
if __name__ == "__main__":
import random
mlist = []
for i in range(100001):
data = random.randint(1,9999)
mlist.append(data)#
print(mlist)
print(finder(mlist))
