使用MaxHeap求解数组第K大元素LeetCode超时，求问题排查与优化方案

现有大顶堆实现的性能/逻辑缺陷 #

你的大顶堆实现存在多处明显问题，是触发超时的核心原因：

• 右孩子索引计算错误：标准数组存储堆的结构中，索引为i的节点右孩子索引应为2*i + 2，你的代码里getRightChildIndex返回2*i，会导致堆化过程中访问错误节点，堆结构不符合大顶堆规则，产生大量无效交换甚至逻辑死循环，大幅增加耗时。
• 扩容逻辑错误：ensureCapacity方法的触发条件capacity == size -1完全错误，初始状态下该条件永远不成立，当插入元素超过初始容量10时会触发数组越界异常，异常处理开销会导致运行时间暴增。正确的扩容判断应为size == capacity。
• 提交代码包含打印语句：findKthLargest方法中存在System.out.println输出逻辑，IO操作的耗时远高于内存计算，是触发超时的直接原因之一，提交OJ代码必须删除所有打印逻辑。

修复上述三个缺陷后，大顶堆的实现逻辑即可正常运行，但该方案的时间复杂度为O(nlogn)，面对大规模测试用例时性能仍有较大优化空间。

效率更高的求解方案 #

小顶堆优化方案 #

不需要将所有n个元素都存入大顶堆，只需维护大小为k的小顶堆存储当前遍历到的前k大元素即可：

• 遍历数组所有元素，若堆大小小于k直接入堆
• 若当前元素大于堆顶元素，弹出堆顶后将当前元素入堆
• 遍历完成后堆顶就是第k大元素

时间复杂度从原来的O(nlogn)降低到O(nlogk)，当k远小于n时性能提升非常明显。

快速选择算法 #

基于快速排序的分区思想实现，平均时间复杂度为O(n)，是理论上最快的解法：

• 随机选择数组中的一个元素作为基准值，将数组分为小于基准、等于基准、大于基准三个部分
• 根据大于基准的元素个数判断第k大元素所在的分区，只递归对应分区即可，不需要处理全量数据

实际运行性能通常优于堆实现，适合处理大规模数据场景。

内容的提问来源于stack exchange，提问作者serah