力扣215数组中的第k个最大元素（堆排序法）

建立一个大根堆做 k−1 次删除操作后堆顶元素就是我们要找的答案前置知识建议看看4分钟学堆排序(手机动画版)_哔哩哔哩_bilibili1.将一个子树调整为大顶堆堆下沉调整把i位置元素放到正确位置保证以i为根的子树满足大顶堆。堆必须是完全二叉树且大顶堆父≥子小顶堆父≤子public void maxHeapify(int[] a, int i, int heapSize) { int l i * 2 1, r i * 2 2, largest i;//计算左右孩子下标 if (l heapSize a[l] a[largest]) {//左孩子存在且大于当前最大值 largest l; } if (r heapSize a[r] a[largest]) { largest r; } if (largest ! i) { swap(a, i, largest); maxHeapify(a, largest, heapSize);//递归,使得整个树变成大顶堆 } }上面这段代码不要想太多只看局部就可以了只看三个数字构成一个二叉树的情况①.(int[] a, int i, int heapSize)能看出来现在在哪个位置处理吗看下面buildMaxHeap就知道了现在的i即从底向上依次遍历非叶子节点②.heapSize / 2 - 1能确保找到倒数第一个非叶子节点吗看下面buildMaxHeap③.参数不是数组吗哪来的子树子树可以理解为数组按照一定顺序排列④.为什么最后递归那一步是maxHeapify(a, largest, heapSize);而不是maxHeapify(a, i, heapSize);不是互换了吗2.将整个数组构建成大顶堆自底向上遍历所有非叶子节点调用maxHeapify把整个数组构建成大顶堆。那么第一个就是最后一个节点×是最后一个非叶子节点public void buildMaxHeap(int[] a, int heapSize) { for (int i heapSize / 2 - 1; i 0; --i) { maxHeapify(a, i, heapSize); } }此时排序问题已经完成了3.找第k大值堆顶和堆末尾元素互换堆的逻辑长度减一然后对新堆顶下沉调整恢复堆不重新建堆public int findKthLargest(int[] nums, int k) { int heapSize nums.length; buildMaxHeap(nums, heapSize); for (int i nums.length - 1; i nums.length - k 1; --i) { swap(nums, 0, i); --heapSize; maxHeapify(nums, 0, heapSize);//新堆顶下沉调整恢复堆 } return nums[0]; }完整代码class Solution { public int findKthLargest(int[] nums, int k) { int heapSize nums.length; buildMaxHeap(nums, heapSize); for (int i nums.length - 1; i nums.length - k 1; --i) { swap(nums, 0, i); --heapSize; maxHeapify(nums, 0, heapSize); } return nums[0]; } public void buildMaxHeap(int[] a, int heapSize) { for (int i heapSize / 2 - 1; i 0; --i) { maxHeapify(a, i, heapSize); } } public void maxHeapify(int[] a, int i, int heapSize) { int l i * 2 1, r i * 2 2, largest i; if (l heapSize a[l] a[largest]) { largest l; } if (r heapSize a[r] a[largest]) { largest r; } if (largest ! i) { swap(a, i, largest); maxHeapify(a, largest, heapSize); } } public void swap(int[] a, int i, int j) { int temp a[i]; a[i] a[j]; a[j] temp; } }