这道题主要考察排序算法，之前用快排写的，发现测试用例改了之后没办法通过了。故改用堆排序。

堆排序由两部分构成：

1.heapify用来调整堆的结构（使堆这种特殊的完全二叉树中的父节点大于两个孩子节点，但两个孩子节点之间没有大小要求）

2.heapsort部分用来将堆的首元素与末尾元素交换，然后再调用heapify使除了末尾元素之外的n-1个元素来继续形成大顶堆，然后再交换首尾元素，再调整使剩下n-2个元素形成堆，循环往复直至堆内只剩下最后一个元素。

根据堆排序的性质，最好最坏平均时间复杂度都为O(nlogn)，且不需要额外开辟空间存储原数组，故空间复杂度O(1)

    def findKth(self , a: List[int], n: int, K: int) -> int:
        def heapify(a, n, i):
            largest = i
            lson = 2 * i + 1
            rson = 2 * i + 2
            if lson < n and a[lson] > a[largest] :
                largest = lson
            if rson < n and a[rson] > a[largest]:
                largest = rson
            if largest != i:
                a[largest], a[i] = a[i], a[largest]
                heapify(a, n, largest)
        def heapsort(a, n):
#            建大顶堆
            for i in range(len(a)//2 - 1, -1 ,-1):
                heapify(a, n, i)
#            排序
            for i in range(len(a) - 1, 0, -1):                       
                a[0], a[i] = a[i], a[0]
                heapify(a, i, 0)
        heapsort(a, n)
        return a[-K]