从零开始，用堆实现求滑动窗口最大值。
通过维护一个大堆来获取最大值及其下标。
遇到一个值就加入堆，在新添加元素后，如果堆顶元素的下标还在滑动窗口范围内，则获取其值。
否则弹出堆顶元素，至堆顶元素的下标在滑动窗口范围内。 
class Solution:
    heap = []
    def __init__(self):
        self.heap = []
    def heapAdjust(self, i, end):
        # 传入根节点下标和边界下标，计算出根节点左孩子下标
        j = 2*i + 1 
        while j <= end: # 左孩子存在
            if j+1 <= end and self.heap[j+1][0] > self.heap[j][0]: # 右孩子存在且更大
                j += 1
            if self.heap[j][0] > self.heap[i][0]: # 孩子比父亲大，交换
                self.heap[j], self.heap[i] = self.heap[i], self.heap[j]
                i = j                             # 更新父子下标，进入下一层
                j = 2*i + 1
            else:
                break         
    def heappush(self, val, idx):
        # 尾插，向上调整，维护一个堆
        self.heap.append((val, idx))
        j = len(self.heap)-1   # 插入元素下标
        while j > 0:
            i = (j-1)//2 # j对应的父节点
            if self.heap[i][0] < self.heap[j][0]: # 孩子大于父亲值，交换
                self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
                j = i    # 更新插入元素的位置
            else:
                break
    def heappop(self):
        # 弹出堆顶元素——最大值
        # 首尾交换
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        pop = self.heap.pop()
        self.heapAdjust(0, len(self.heap)-1)
        return pop
    def gettop(self):
        return self.heap[0]
    
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        if not num: return []
        maxIW = []
        for i in range(len(num)):
            # 先构造大小为size的堆
            if i < size:
                self.heappush(num[i], i)
            else:
                maxIW.append(self.gettop()[0])     # 存入当前堆的最大值
                self.heappush(num[i], i)
                while self.gettop()[1]<=i-size:  # 判断最大值是否在滑动窗口内，如果不在则不断弹出堆顶元素
                    self.heappop()
        maxIW.append(self.gettop()[0])     # 存入当前堆的最大值
        return maxIW