為什麼要把這兩個算法放在一起呢，這兩個算法都用了空間換時間的方法來維護對應的值。
雙堆棧維護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))