题解 | #最小的K个数#

class Solution:
    # 小根堆调整函数，静态方法
    @staticmethod
    def heapAdjust(lis, i, end):
        j = 2*i + 1     # 根节点的左孩子的下标
        while j <= end: # 左孩子存在
            if j+1 <= end and lis[j+1] < lis[j]: # 右孩子存在，且小于左孩子，j指向右孩子
                j += 1
            if lis[i] > lis[j]: # 父大于子，交换
                lis[i], lis[j] = lis[j], lis[i]
                i = j
                j = 2*i + 1
            else:
                break
    # 建小根堆函数
    def heaplify(self, lis):
        length = len(lis)
        for i in range((length-1-1)//2, -1, -1):# 逆向遍历所有非叶子节点
            self.heapAdjust(lis, i, length-1)
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        if not k:return []
        self.heaplify(input)
        for i in range(1, k+1):
            input[0], input[-i] = input[-i], input[0]
            self.heapAdjust(input, 0, len(input)-i-1)
        return input[-k:]