题解 | #最小的K个数#——使用最大堆排序解

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param input int整型一维数组
# @param k int整型
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        # write code here
        input = self.heapsort(input)
        print(input)
        return input[0:k]

    def heapify(self,arr,n,i):
        '''
        :param arr: 存储堆的数组
        :param n: 数组长度
        :param i: 待维护节点的下标
        :return:
        '''
        largest = i
        #假设父节点最大，找到左节点、右节点下标
        left = i*2+1
        right = i*2+2

        if left<n and arr[largest]<arr[left]:
            largest = left
        if right<n and arr[largest]<arr[right]:
            largest = right
        if largest != i:
            arr[i],arr[largest]=arr[largest],arr[i]
            self.heapify(arr,n,largest)

    def heapsort(self,arr):
        #建堆
        n = len(arr)
        for i in range(n,-1,-1):
            self.heapify(arr,n,i)
        #排序
        for i in range(n-1,0,-1):
            arr[i],arr[0]=arr[0],arr[i]
            self.heapify(arr,i,0)
            # 重新维护剩余i个元素
        return arr