双堆维护中位数和双堆栈维护max/min值

为什么要把这两个算法放在一起呢，这两个算法都用了空间换时间的方法来维护对应的值。

双堆栈维护max或者min的思路是：

1. 当加入元素的时候，首先一个堆栈来存放新加入的元素。

2. 和第二个元素的尾部比较（也就是它的最大值，这里需要考虑刚开始的时候需要直接存放上去），如果加入元素比最大值大，我们把元素放入第二个堆栈中。

3. 如果比最大元素小我们就把最大值再次压入堆栈。

4. 在弹出元素的时候，我们一次弹出第一个堆栈和第二个堆栈的末尾元素即可

代码如下：

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. 构造两个堆， 一个大顶堆， 一个小顶堆。
2. 把第一个元素拿出来设置为中位数，
3. 再拿出第二个元素，如果比中位数大，则放在小顶堆中，如果比中位数小，则放在大顶堆中。
4. 左右两个堆的大小不能大于1，当出现大于1的情况时，我们需要动态改变堆的大小， 请看5
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))