从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;  // 无效输入，返回一个无效值
        }
        // 构建最大堆
        buildMaxHeap(nums);
        // 进行堆排序
        //从nums数组的最后一个元素开始，递减地遍历到第(nums.length - k + 1)个元素。其中nums.length是数组的长度，k是要找的第K个最大元素的位置。
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            //下沉堆顶最大元素，并断开树的链接
            swap(nums, 0, i);  // 将堆顶元素与当前末尾元素交换
            maxHeapify(nums, i, 0);  // 调整堆，保持最大堆性质
        }
        // 返回第 k 个最大元素
        return nums[0];
    }
    // 构建最大堆
    private void buildMaxHeap(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, n, i);
        }
    }
    // 调整堆，保持最大堆性质
    private void maxHeapify(int[] nums, int heapSize, int index) {
        int largest = index;  // 假设当前节点最大
        int left = 2 * index + 1; // 获取左节点
        int right = 2 * index + 2;// 获取右节点
        // 如果左子节点存在且大于 当前节点 的值
        // 则更新 largest 为左子节点的索引
        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        // 如果右子节点存在且大于 当前节点 和 左子节点 的值
        // 则更新 largest 为右子节点的索引
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
        //如果 largest 不等于当前节点的索引，说明当前节点不是最大的，
        //则将当前节点与 largest 所指的节点进行交换，以保证最大值上浮到当前节点位置。
        if (largest != index) {
            swap(nums, index, largest);  // 将当前节点与最大节点交换
            //递归调用 maxHeapify，以便在交换后继续对 largest 所指的子节点进行堆化操作，以保持最大堆的性质。
            maxHeapify(nums, heapSize, largest);  // 递归调整子堆
        }
    }
    // 交换数组中两个元素的位置
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}