最小k个数.org

题目

思路

堆排序后取前k个值

code

#堆排序
        def build_heap(arr, root, end):
            while 1:
                child = 2*root+1
                if child > end:
                    break
                if child+1 <= end and arr[child+1] > arr[child]:
                    child += 1
                if arr[root] < arr[child]:
                    arr[root], arr[child] = arr[child], arr[root]
                    root = child
                else:
                    break

        def heap_sort(arr):
            n = len(arr)
            first_root = n//2 -1
            for root in range(first_root, -1, -1):
                build_heap(arr, root, len(arr)-1)
            for end in range(len(arr)-1, 0, -1):
                arr[0], arr[end] = arr[end], arr[0]
                build_heap(arr, 0, end-1)

        heap_sort(arr)
        return arr[:k]