题解 | #最小的K个数#

# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        n = len(input)
        # 特殊无返回情况
        if n == 0 or k == 0 or n < k:
            return []

        heap = input.copy()

        self.build_max_heap(heap, k)

        for i in range(k, n):
            if heap[0] > heap[i]:
                heap[0], heap[i] = heap[i], heap[0]
                self.max_heapify(heap, 0, k)
        return heap[:k]

    '''
    arr:输入数组
    k:堆的大小
    '''
    def build_max_heap(self, arr: List[int], k) -> None:
        # 从最后一个非叶结点从后往前进行堆的构建
        for i in range(k // 2 - 1, -1, -1):
            self.max_heapify(arr, i, k)
    '''
    arr:输入数组
    i:当前索引
    n:堆总长
    '''
    def max_heapify(self, arr: List[int], i: int, n: int):
        # 根节点是0号节点
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        # 如果根节点不是最大值(此步骤是为了跟踪最大值，方便后续更新）
        if left < n and arr[largest] < arr[left]:
            largest = left
        if right < n and arr[largest] < arr[right]:
            largest = right
        # 根节点非最大值需要交换根节点，实行最大堆化
        if largest != i:
            arr[largest], arr[i] = arr[i], arr[largest]
            self.max_heapify(arr, largest, n)

    # def heap_sort(self, arr: List[int]) -> None:
    #     # 构建初始堆后通过交换根到队尾来实现排序
    #     n = len(arr)
    #     self.build_max_heap(arr)
    #     for i in range(n - 1, 0, -1):
    #         arr[0], arr[n] = arr[n], arr[0]
    #         self.max_heapify(arr, i, n)

• 有点痛苦，先写了一键排序，然后写堆排序（查询后）。
• 利用堆排序主要想到的优点是：
• 节省时间复杂度，使其从O(Nlog2N)下降到O(Nlog2K)，而空间复杂度从O(1)上升到O(K)可以忽略不计。
• 协同于升序最大堆降序最小堆，本题应该采用最大堆解决问题（把大的数据移到数组后面舍弃掉），即：
• 任意元素小于当前最大堆的最大值，将其囊括进最大堆，构建新的最小数组