【剑指offer】最小的K个数（python）

1. 维护一个大顶堆来找最小值。
堆是一个完全二叉树，每个结点值都 ≥ 孩子结点值就是大顶堆，每个结点值都 ≤ 孩子结点值就是小顶堆。每次将堆顶的结点（序列中的最大值 or 最小值）与序列末尾元素交换，这样有序序列元素就 +1，无序序列元素就 -1，对新的无序序列重复操作，从而实现排序。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)，前 K 个值就是最小的 K 个数。
2. 完全二叉树的结构性质
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
第一个非叶子结点：arr.length / 2 - 1
3. 堆排序操作顺序
从左至右，从下至上进行调整。结点指针就是数组的索引。

代码参考

# -*- coding:utf-8 -*-
class Solution:
    def build_maxheap(self,arr,root,end):
        while True:
            child = 2 * root + 1 # 从左孩子开始
            if child > end: # 循环终止条件，孩子指针位置超过了末尾元素位置
                break
            if child + 1 <= end and arr[child + 1]>arr[child]: # 右孩子大于左孩子，指向右孩子
                child += 1
            if arr[child] > arr[root]: # 如果最大的孩子大于父节点，交换
                arr[child],arr[root] = arr[root],arr[child]
                root = child
            else:
                break
    def heap_sort(self,arr):
        n = len(arr)
        first_root = n // 2 - 1 
        for root in range(first_root,-1,-1): # 从最深的根节点往前遍历，建堆调整
            self.build_maxheap(arr,root,n-1)
        for end in range(n-1,0,-1): # 建堆完成，堆顶arr[0]为最大元素，调整到末尾，对剩下的元素建堆
            arr[0], arr[end] = arr[end], arr[0]
            self.build_maxheap(arr, 0, end - 1)
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput) < k:
            return []
        else:
            self.heap_sort(tinput)
            return tinput[:k]