# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        # lentinput = len(tinput)
        # a = []
        # if(lentinput < k):
        #     return a
        # tinput.sort()
        # for i in range(k):
        #     a.append(tinput[i])
        # return a

        # 创建或插入最大堆
        def creatMaxHeap(num, maxHeap):
            maxHeap.append(num)
            currentIndex = len(maxHeap) - 1
            while currentIndex != 0:
                parentIndex = (currentIndex - 1) >> 1
                if maxHeap[parentIndex] < maxHeap[currentIndex]:
                    maxHeap[parentIndex], maxHeap[currentIndex] = maxHeap[currentIndex], maxHeap[parentIndex]
                    currentIndex = parentIndex
                else:
                    break
            return maxHeap

        # 调整最大堆，头结点发生改变
        def adjustMaxHeap(num, maxHeap):
            if num < maxHeap[0]:
                maxHeap[0] = num
            index = 0
            maxHeapLen = len(maxHeap)
            while index < maxHeapLen:
                leftIndex = index * 2 + 1
                rightIndex = index * 2 + 2
                lagerIndex = 0
                if rightIndex < maxHeapLen:
                    if maxHeap[rightIndex] < maxHeap[leftIndex]:
                        lagerIndex = leftIndex
                    else:
                        lagerIndex = rightIndex
                elif leftIndex < maxHeapLen:
                    lagerIndex = leftIndex
                else:
                    break
                if maxHeap[index] < maxHeap[lagerIndex]:
                    maxHeap[index], maxHeap[lagerIndex] = maxHeap[lagerIndex], maxHeap[index]
                index = lagerIndex
            return maxHeap

        maxHeap = []
        inputLen = len(tinput)
        if inputLen < k or k <= 0:
            return []

        for i in range(inputLen):
            if i < k:
                maxHeap = creatMaxHeap(tinput[i], maxHeap)
                print(maxHeap)
            else:
                maxHeap = adjustMaxHeap(tinput[i], maxHeap)
        maxHeap.sort()
        return maxHeap


# tinput = [0,1,1,1,4,5,3,7,7,8,10,2,7,8,0,5,2,16,12,1,19,15,5,18,2,2,22,15,8,22,17,6,22,6,22,26,32,8,10,11,2,26,9,12,9,
#           7,28,33,20,7,2,17,44,3,52,27,2,23,19,56,56,58,36,31,1,19,19,6,65,49,27,63,29,1,69,47,56,61,40,43,10,71,60,66,
#           42,44,10,12,83,69,73,2,65,93,92,47,35,39,13,75]
# k = 75
# print(tinput[10])
# s = Solution()
# out = s.GetLeastNumbers_Solution(tinput, k)
# print(out)