随时找到数据流的中位数

这题只能用最小最大堆做，二分法插入也太慢。
翻到最下面有C++的大佬的参考答案。
这种题目好意思叫中等题？考试你用半个小时手写一个堆的定义出来？
用例通过率: 100.00% 运行时间: 2751ms 占用内存: 33024KB。
代码源自https://blog.csdn.net/qq_34342154/article/details/78454581?utm_source=blogxgwz8

class HeapNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

class MyHeap:
    def __init__(self, comp):
        self.head = None    #堆头节点
        self.last = None    #堆尾节点
        self.size = 0    #当前堆的大小
        self.comp = comp    #基于比较器决定是大根堆还是小根堆

    def getHead(self):
        return self.head.value if self.head != None else None

    def getSize(self):
        return self.size

    def isEmpty(self):
        return True if self.size == 0 else False

    #添加一个新节点到堆中
    def add(self, value):
        newNode = HeapNode(value)
        if self.size == 0:
            self.head = newNode
            self.last = newNode
            self.size = 1
            return
        node = self.last
        parent = node.parent   
        #找到尾节点的下一个位置并插入新节点
        while parent != None and parent.left != node:
            node = parent
            parent = node.parent
        if parent == None:
            nodeToAdd = self.mostLeft(self.head)
            nodeToAdd.left = newNode
            newNode.parent = nodeToAdd
        elif parent.right == None:
            parent.right = newNode
            newNode.parent = parent
        else:
            nodeToAdd = self.mostLeft(parent.right)
            nodeToAdd.left = newNode
            newNode.parent = nodeToAdd
        self.last = newNode
        #建堆过程及其调整
        self.heapInsertModify()
        self.size += 1

    def heapInsertModify(self):
        node = self.last
        parent = node.parent
        if parent != None and self.comp(parent.value, node.value):
            self.last = node.parent
        while parent != None and self.comp(parent.value, node.value):
            self.swapClosedTwoNode(node, parent)
            parent = node.parent
        if self.head.parent != None:
            self.head = self.head.parent

    def swapClosedTwoNode(self, node, parent):
        if node == None or parent == None:
            return 
        parentParent = parent.parent
        parentLeft = parent.left
        parentRight = parent.right
        nodeLeft = node.left
        nodeRight = node.right
        node.parent = parentParent
        if parentParent != None:
            if parentParent.left == parent:
                parentParent.left = node
            else:
                parentParent.right = node
        parent.parent = node
        if nodeLeft != None:
            nodeLeft.parent = parent
        if nodeRight != None:
            nodeRight.parent = parent
        if node == parentLeft:
            node.left = parent
            node.right = parentRight
            if parentRight != None:
                parentRight.parent = node
        else:
            node.left = parentLeft
            node.right = parent
            if parentLeft != None:
                parentLeft.parent = node
        parent.left = nodeLeft
        parent.right = nodeRight

    def mostLeft(self,node):
        while node.left != None:
            node = node.left
        return node

    def mostRight(self, node):
        while node.right != None:
            node = node.right
        return node

    def popHead(self):
        if self.size == 0:
            return None
        res = self.head
        if self.size == 1:
            self.head = None
            self.last = None
            self.size = 0
            return res.value
        oldLast = self.popLastAndSetPreviousLast()  #返回尾节点并更新尾节点
        #如果弹出尾节点，堆的大小等于1的处理
        if self.size == 1:
            self.head = oldLast
            self.last = oldLast
            return res.value
        #如果弹出尾节点，堆的大小大于1的处理
        headLeft = res.left
        headRight = res.right
        oldLast.left = headLeft
        if headLeft != None:
            headLeft.parent = oldLast
        oldLast.right = headRight
        if headRight != None:
            headRight.parent = oldLast
        res.left = None
        res.right = None
        self.head = oldLast
        #堆heapify过程
        self.heapify(self.head)
        return res.value

    def heapify(self, node):
        left = node.left
        right = node.right
        most = node
        while left != None:
            if left != None and self.comp(most.value, left.value):
                most = left
            if right != None and self.comp(most.value, right.value):
                most = right
            if most == node:
                break
            else:
                self.swapClosedTwoNode(most, node)
            left = node.left
            right = node.right
            most = node
        if node.parent == self.last:
            self.last = node
        while node.parent != None:
            node = node.parent
        self.head = node

    def popLastAndSetPreviousLast(self):
        node = self.last
        parent = node.parent  #以下是寻找尾节点的上一个节点
        while parent != None and parent.right != node:
            node = parent
            parent = node.parent
        if parent == None:
            node = self.last
            parent = node.parent
            node.parent = None
            if parent != None:
                parent.left = None
            self.last = self.mostRight(self.head)
        else:
            newLast = self.mostRight(parent.left)
            node = self.last
            parent = node.parent
            node.parent = None
            if parent.left == node:
                parent.left = None
            else:
                parent.right = None
            self.last = newLast
        self.size -= 1
        return node

def minHeapComparator(a, b):
    if a <= b:
        return False
    if a > b:
        return True

def maxHeapComparator(a, b):
    if a >= b:
        return False
    else:
        return True


class MedianHolder:
    def __init__(self):
        self.minHeap = MyHeap(minHeapComparator)
        self.maxHeap = MyHeap(maxHeapComparator)

    def addNum(self, num):
        if self.maxHeap.isEmpty():
            self.maxHeap.add(num)
            return
        if self.maxHeap.getHead() >= num:
            self.maxHeap.add(num)
        else:
            if self.minHeap.isEmpty():
                self.minHeap.add(num)
            elif self.minHeap.getHead() > num:
                self.maxHeap.add(num)
            else:
                self.minHeap.add(num)
        self.modifyTwoHeapSize()

    def modifyTwoHeapSize(self):
        if self.minHeap.getSize() == self.maxHeap.getSize() + 2:
            self.maxHeap.add(self.minHeap.popHead())
        if self.maxHeap.getSize() == self.minHeap.getSize() + 2:
            self.minHeap.add(self.maxHeap.popHead())

    def getMedian(self):
        maxHeapSize = self.maxHeap.getSi***HeapSize = self.minHeap.getSize()
        if maxHeapSi***HeapSize == 0:
            return None
        if (maxHeapSi***HeapSize) & 1 == 0:
            return (self.maxHeap.getHead() + self.minHeap.getHead()) / 2
        else:
            if maxHeapSize > minHeapSize:
                return self.maxHeap.getHead()
            else:
                return self.minHeap.getHead()

#
# the medians
# @param operations int整型二维数组 ops
# @return double浮点型一维数组
#
class Solution:
    def flowmedian(self , operations ):
        ans=[]
        s=MedianHolder()
        for i in operations:
            if i[0]==1:
                s.addNum(i[1])
            elif i[0]==2:
                if s.getMedian():
                    ans.append(s.getMedian())
                else:
                    ans.append(-1)
        return ans

啊有参考答案：用例通过率: 100.00% 运行时间: 110ms 占用内存: 11976KB

class Solution {
public:
  /**
   * the medians
   * @param operations int整型vector<vector<> ops
   * @return double浮点型vector
   */
  vector<double> flowmedian(vector<vector<int>> & operations) {
    // write code here
    vector<double> res;
    for(auto ops: operations){
      if(ops[0] == 1){
        put(ops[1]);
      }else{
        res.push_back(get());
      }
    }
    return res;
  }

  multiset<int> nums;
  multiset<int>::iterator it = nums.end();
  void put(int x){
    int n = nums.size();
    nums.insert(x);
    if(n==0){
      it = nums.begin();
    }else{
      if(n&1){
        it = x < *it ? it : ++it;
      }else{
        it = x < *it ? --it: it;
      }
    }
  }

  double get(){
    if(nums.size() == 0){
      return -1;
    }
    return (*it + *prev(it, 1 - (nums.size()&1)))*0.5;
  }
};