数组中的第K个最大元素

2025/10/16

思路：遍历构造最大堆，然后删除K次根节点

手写代码：

class MaxHeap:

    def __init__(self, elements):
        self.h = [nan] * len(elements)
        self.len = 0
        for e in elements:
            self.insert(e)
            self.len += 1

    def insert(self, e):
        self.h.append(e)
        self.len += 1
        if self.h[self.len // 2] < e:
            temp = self.h[self.len // 2]
            self.h[self.len // 2] = self.h[self.len]
            self.h[self.len] = temp

    def delete(self, index):
        self.h[index] = self.h[self.len-1]
        self.h[self.len-1]
        self.len -= 1

        t = index
        while t < self.len:
            if self.h[2t - 1] > self.h[t]:
                if self.h[2t] > self.h[2t - 1]:
                    temp = self.h[t]
                    self.h[t]  = self.h[2t] 
                    self.h[2t] = temp
                    t = 2t
                else: 
                    temp = self.h[t]
                    self.h[t]  = self.h[2t-1] 
                    self.h[2t-1] = temp
                    t = 2t -1
        
def Kth(nums, k):
    h = MaxHeap(nums)
    for i in range(k):
        h.delete(index=0)
    return h.h[0]

答案：记住堆就秒了