题解 | #寻找第K大#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        def heapify(arr, n, i):
            """
            维护一个父节点为i的最小堆
            """
            l = 2*i + 1
            r = 2*i + 2
            small = i
            if l<n and arr[l] < arr[small]:
                small = l
            if r<n and arr[r] < arr[small]:
                small = r
            if i != small:
                arr[small], arr[i] = arr[i], arr[small]
                heapify(arr, n, small)
            
        def buildMinHeap(arr, K):
            """
            构建前k个元素的最小堆
            """
            n = len(arr)
            last_parent = (K-1)//2
            for i in range(last_parent, -1, -1):
                heapify(arr, K, i)
        
        def updateHeap(arr, item):
            """
            item比堆顶大，更新最小堆
            """
            if item > arr[0]:
                arr[0] = item
                heapify(arr, K, 0)
                
        buildMinHeap(a, K)
        for item in range(K, n):
            updateHeap(a, a[item])
            
        """
        最大的k个元素生成的最小堆，堆顶就是第k大
        """
        return a[0]