数组中的第K个最大元素

本文详细讲解了如何通过构建最大堆和堆排序来解决 LeetCode 215 题“数组中的第K个最大元素”，并提供了完整的 Python 实现。

Leetcode Python 堆排序算法

阅读要点

最大堆的构造方法：从最后一个非叶子节点开始，自底向上调整。
堆排序的步骤：交换堆顶与末尾元素，调整剩余堆，重复直至完成。
通过堆排序后，数组降序排列，第 k 个元素即为第 k 个最大元素。

开始写作

解法

最大堆的构造方法

在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。

假设树的节点个数为 n，以 1 为下标开始编号，直到 n 结束。对于节点 i，其父节点为 i/2；左孩子节点为 i2，右孩子节点为 i2+1。最后一个节点的下标为 n，其父节点的下标为 n/2。

排序方法

交换堆顶与末尾元素：将堆顶元素（最大值）与当前未排序部分的最后一个元素交换。
调整剩余堆：对剩余未排序部分重新调整为最大堆。
重复步骤 1 和 2，直到所有元素排序完成。

答案

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        def adjustDown(p_id, end_id):
            left = p_id * 2 + 1
            right = p_id * 2 + 2
            max_id = p_id
            if left <= end_id and nums[left] > nums[max_id]:
                max_id = left
            if right <= end_id and nums[right] > nums[max_id]:
                max_id = right
            if max_id == p_id:
                return 
            nums[max_id], nums[p_id] = nums[p_id], nums[max_id]
            adjustDown(max_id, end_id)
        
        n = len(nums)
        # 构建最大堆
        for i in range((n-2)//2, -1, -1):
            adjustDown(i, n-1)
        # 堆排序
        for i in range(n-1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            adjustDown(0, i-1)
        return nums[k-1]