def left(i):
	""" 求节点i的左子树 """
	return 2 * i + 1


def right(i):
	""" 求节点i的右子树，在数组中，右子树比左子树大1 """
	return left(i) + 1


def exchange(arr, i, j):
	""" 交换数组中两个位置的值 """
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp


def heapify(arr, i, size):
	""" 维护最小堆 """
	l, r, small = left(i), right(i), 0
	# small保存较小的那个值
	if l < size and arr[l] < arr[i]:
		small = l
	else:
		small = i
	if r < size and arr[r] < arr[small]:
		small = r
	if small != i:
		# 当前节点与较小的值
		exchange(arr, i, small)
		# 递归进行维护堆
		heapify(arr, small, size)


def make_heap(arr):
	""" 构建一个最小堆 """
	alen = len(arr)
	for i in range(alen // 2, -1, -1):
		heapify(arr, i, alen)


class Solution:
	def GetLeastNumbers_Solution(self, tinput: list, k):
		make_heap(tinput)
		alen = len(tinput)
		res = []
		for i in range(k):
			# 从最小堆中取出第一个节点的值，这个值是最小值
			res.append(tinput[0])
			# 将当前节点废弃，
			exchange(tinput, 0, alen - 1)
			alen -= 1
			# 重新维护堆
			heapify(tinput, 0, alen)
		return res