Java如何使用PriorityQueue以O(n)时间从数组构建最大堆查找第K大元素

基于JDK自带PriorityQueue实现O(n)建堆 #

• JDK的PriorityQueue默认是最小堆，要构建最大堆需要传入逆序比较器Collections.reverseOrder()
• 不要逐个调用offer()方法插入元素（该操作时间复杂度为O(nlogn)），直接使用带集合参数的构造方法即可，该方法底层调用heapify()批量建堆，时间复杂度为O(n)
• 原代码的循环中缺少k--逻辑，会导致死循环，需要补充

完整代码如下：

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public int findKthLargest(int[] nums, int k) {
    // O(n)时间构建最大堆
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        Arrays.stream(nums).boxed().collect(Collectors.toList()),
        Collections.reverseOrder()
    );
    
    // 移除k-1个最大元素
    while (k > 1) {
        pq.poll();
        k--;
    }
    
    return pq.peek();
}

手动实现堆（性能更优） #

如果要避免自动装箱、集合转换的额外开销，可以手动实现heapify逻辑，直接在原数组上建堆，性能更高：

public int findKthLargest(int[] nums, int k) {
    int heapSize = nums.length;
    // O(n)建最大堆：从最后一个非叶子节点开始逐个下沉
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
        siftDown(nums, heapSize, i);
    }

    // 移除k-1个堆顶元素
    for (int i = 0; i < k - 1; i++) {
        swap(nums, 0, heapSize - 1);
        heapSize--;
        siftDown(nums, heapSize, 0);
    }

    return nums[0];
}

// 节点下沉操作
private void siftDown(int[] nums, int heapSize, int index) {
    while (true) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heapSize && nums[leftChild] > nums[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && nums[rightChild] > nums[largest]) {
            largest = rightChild;
        }

        if (largest == index) break;
        swap(nums, index, largest);
        index = largest;
    }
}

private void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

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