堆

当年学数据结构的时候，不知道这些结构，到底有什么用。背啊背啊，就忘记了。
最近工作中，一直在“大数据”规模，处理大批量时序数据。也遇到时间窗口中的计算。这样的场景中，堆就坡有实用价值。每当一个新的序列数据到来，堆都需要为这个新元素做调整：

序列数据和堆.png

根据不同的场景，调整的规则不同：

1. 序列中的k-th元素。这个场景，是就全局序列数据而言，找到k-th元素。每个新元素加入，都要调整一下堆

import heapq
class Solution(object):
    def __init(self, nums:List[int], k:int):
        self.nums = nums
        self.k = k
        heapq.heapify(nums)
        while len(nums) > k:
            heapq.heappop(nums)

    def add(self, e:int) -> int:
        if len(self.nums) < self.k:
            heapq.heappush(nums, e)
        elif nums[0] < e:
            heapq.headreplace(nums, e)
        return nums[0]

2. 窗口滑动过程中，出现的每个最大值。除了原始的序列数组，我们还需要构建一个窗口数组（由序列数组元素的下标组成）和一个结果数组（存放每个窗口的最大值）

def slidingWindow(self, nums:List[int], k:int) -> List[int]:
    if len(nums) == 0:
        return []
    window, result = [], [] #window扮演堆的角色
    for i,x in enumerate(nums):
        if i >= k and window[0] <= i - k: #这个条件表示，当一个新元素到来，发现window需要调整了
            window.pop(0)
        while window and nums[window[-1]] < nums[i]: #这个条件表示，新元素导致window内的小于当前新元素的，都要被干掉
            window.pop()
        window.append(i) #不论新元素，有没有造成窗口调整，都要被加进来
        if i >= k - 1 #当窗口按照规则，被塞满之后，结果集才会被启用
            result.append(nums[0])
    return result