4.22 运用最小堆

Python语言中的堆为最小堆，所以用Python刷题都是在最小堆的基础上。

先说一个结论：最大堆解决取最小的问题，最小堆解决取最大的问题

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

例如
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

根据之前的结论，取最小用大根堆。那具体的思路是：
维护长度为k的大根堆，新的数和堆顶元素比较，如果小于堆顶，则堆顶出来，新的元素进去，这样的k个元素就是最小的。

其实和堆顶元素的比较，就是和当前第k小的元素（守门员）比较的过程，你赢了你就有资格进去，守门员爬。

而Python的堆是小根堆，所以解题的时候需要取相反数，问题转化为用小根堆找相反数arr中最大的k个值。
代码如下：

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return list()
		#初始化长度为k的堆
        hp = [-x for x in arr[:k]]
        heapq.heapify(hp)
        for i in range(k, len(arr)):
            if -hp[0] > arr[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -arr[i])
        ans = [-x for x in hp]
        return ans