class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return heapq.nsmallest(k, arr)

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

class Solution:
    def heapify(self, arr, i):  # 大顶堆化
        left, right = 2 * i + 1, 2 * i + 2
        largest = i
        if left < len(arr) and arr[left] > arr[largest]:
            largest = left
        if right < len(arr) and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[largest], arr[i] = arr[i], arr[largest]
            self.heapify(arr, largest)  # 交换后再次与左右子节点比较

    def build_heap(self, nums):  # 从非叶子节点初始化堆
        for i in range(len(nums) // 2 - 1, -1, -1):
            self.heapify(nums, i)

    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k <= 0:
            return []
        if len(arr) <= k:
            return arr
        
        heap = arr[:k]
        self.build_heap(heap)
        
        for i in range(k, len(arr)):
            if arr[i] < heap[0]:  # 当前元素比k堆顶小时，弹出堆顶并插入当前元素
                heap[0] = arr[i]
                self.heapify(heap, 0)
        return heap

class Solution:
    def partition(self, arr, left, right):
        pivot = left
        i = j = pivot + 1
        while j <= right:
            if arr[j] < arr[pivot]:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
            j += 1
        arr[pivot], arr[i-1] = arr[i-1], arr[pivot]
        return i-1
    
    def quick_sort(self, arr, left, right, k):
        pivot = self.partition(arr, left, right)
        if pivot + 1 == k:
            return
        elif pivot + 1 > k:  # topk元素全在基准左侧
            self.quick_sort(arr, left, pivot - 1, k)
        else:  # topk元素全在基准右侧
            self.quick_sort(arr, pivot + 1, right, k)

    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k <= 0:
            return []
        if len(arr) <= k:
            return arr
        self.quick_sort(arr, 0, len(arr) - 1, k)
        return arr[:k]