python 代码

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):

        retList = []


        def createMaxHeap(num):
            retList.append(num)

            currentIndex = len(retList) - 1

            while currentIndex:
                parrentIndex = (currentIndex - 1) // 2

                if retList[parrentIndex] < retList[currentIndex]:
                    retList[parrentIndex], retList[currentIndex] = retList[currentIndex], retList[parrentIndex]
                    currentIndex = parrentIndex

                else:
                    break

        def adjustMaxHeap(num):
            if retList[0] > num:
                retList[0] = num

            maxHeapLength = len(retList)
            currentIndex = 0

            while currentIndex < maxHeapLength:

                leftIndex = currentIndex * 2 + 1
                rightIndex= currentIndex * 2 + 2  ####

                largerIndex = 0
                if rightIndex < maxHeapLength:
                    if retList[leftIndex] < retList[rightIndex]:
                        largerIndex = rightIndex

                    else:
                        largerIndex = leftIndex

                elif leftIndex < maxHeapLength:
                    largerIndex = leftIndex

                else:
                    break


                if retList[currentIndex] < retList[largerIndex]:
                    retList[currentIndex], retList[largerIndex] = retList[largerIndex], retList[currentIndex]
                    currentIndex = largerIndex

                else:
                    break

        if not input or k < 1:
            return list()

        for i in range(len(input)):
            if i < k:
                createMaxHeap(input[i]) 

            else:

                adjustMaxHeap(input[i])

        retList.sort()
        return retList