python实现最大堆最小堆

样例

class MaxHeap:
    def __init__(self):
        self.heap = []

    def top(self):
        return self.heap[0]

    def push(self, num):
        self.heap.append(num)
        i = len(self.heap)-1
        while i >= 1:
            father = i-1 >> 1
            if self.heap[father] < self.heap[i]:
                self.heap[i], self.heap[father] = self.heap[father], self.heap[i]
                i = father
            else:
                break

    def heapify(self, size, root):
        left = root*2+1
        right = root*2+2
        larger = root
        if left < size and self.heap[larger] < self.heap[left]:
            larger = left
        if right < size and self.heap[larger] < self.heap[right]:
            larger = right
        if larger != root:
            self.heap[larger], self.heap[root] = self.heap[root], self.heap[larger]
            self.heapify(size, larger)

    def pop(self):
        tmp = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heapify(len(self.heap)-1, 0)
        self.heap.pop(-1)
        return tmp

    def size(self):
        return len(self.heap)

class MinHeap:
    def __init__(self):
        self.heap = []

    def top(self):
        return self.heap[0]

    def push(self, num):
        self.heap.append(num)
        i = len(self.heap)-1
        while i >= 1:
            father = i-1 >> 1
            if self.heap[father] > self.heap[i]:
                self.heap[i], self.heap[father] = self.heap[father], self.heap[i]
                i = father
            else:
                break

    def heapify(self, size, root):
        left = root * 2 + 1
        right = root * 2 + 2
        smaller = root
        if left < size and self.heap[smaller] > self.heap[left]:
            smaller = left
        if right < size and self.heap[smaller] > self.heap[right]:
            smaller = right
        if smaller != root:
            self.heap[smaller], self.heap[root] = self.heap[root], self.heap[smaller]
            self.heapify(size, smaller)

    def pop(self):
        tmp = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heapify(len(self.heap)-1, 0)
        self.heap.pop(-1)
        return tmp

    def size(self):
        return len(self.heap)

class Solution:
    def __init__(self):
        self.maxheap = MaxHeap()
        self.minheap = MinHeap()
    def insert(self, num):
        """
        :type num: int
        :rtype: void
        """
        self.maxheap.push(num)
        if self.maxheap.size() > self.minheap.size()+1:
            self.minheap.push(self.maxheap.pop())
        while self.minheap.size() and self.maxheap.top() > self.minheap.top():
            t1 = self.maxheap.pop()
            t2 = self.minheap.pop()
            self.minheap.push(t1)
            self.maxheap.push(t2)



    def getMedian(self):
        """
        :rtype: float
        """
        n1 = self.maxheap.size()
        n2 = self.minheap.size()
        return (self.maxheap.top()+self.minheap.top())/2.0 if n1 == n2 else self.maxheap.top()