题解 | #最小的K个数#

# -*- coding:utf-8 -*-
class Solution:
	# 调整堆
    def maxHeapify(self, arr, i, heapSize):
        l = 2 * i + 1
        r = l + 1
        largest = i
        if l < heapSize and arr[l] > arr[largest]:
            largest = l
        if r < heapSize and arr[r] > arr[largest]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self.maxHeapify(arr, largest, heapSize)
	# 构建堆
    def buildMaxHeap(self, arr):
        for i in range(len(arr)//2-1, -1, -1):
            self.maxHeapify(arr, i, len(arr))
	# 堆排序    
    def heapSort(self, arr):
        self.buildMaxHeap(arr)
        for i in range(len(arr)-1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            self.maxHeapify(arr, 0, i)
    
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        self.heapSort(tinput)
        return tinput[:k]