为何PriorityQueue实现求第k大整数比排序法更慢？

我针对「求数组中第k大整数」问题实现了两种解决方案：

• 第一种使用PriorityQueue，原以为时间复杂度是O(n)，实际应为O(nlogk)；
• 第二种直接排序数组后返回对应元素，时间复杂度为O(nlogn)。

但在对超大数组（长度为1亿）进行基准测试时，针对多种k值（例如k为数组长度的一半），排序法的运行速度明显快于PriorityQueue实现。测试输出如下：

priority queue method time in seconds = 78.194
sort method time in seconds = 9.864

我的代码：

import java.util.PriorityQueue;
import java.util.Random;
import java.util.Arrays;

public class KthLargestElement {

    public static void main(String[] args) {
        int n = 100000000;
        int k = n/2;
        int[] numbers = intsInRange(n, 0, n*100);

        long start = System.currentTimeMillis();
        kthLargestPriorityQueueMethod(numbers, k);
        System.out.println("priority queue method time in seconds = " + (double)(System.currentTimeMillis() - start)/1000.0);

        start = System.currentTimeMillis();
        kthLargestSortMethod(numbers, k);
        System.out.println("sort method time in seconds = " + (double)(System.currentTimeMillis() - start)/1000.0);
    }

    private static int kthLargestSortMethod(int[] numbers, int k) {
        Arrays.sort(numbers);
        return numbers[numbers.length - k];
    }

    private static int kthLargestPriorityQueueMethod(int[] numbers, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i : numbers){
            q.offer(i);

            if(q.size() > k){
                q.poll();
            }
        }

        return q.peek();
    }

    private static int[] intsInRange(int size, int lowerBound, int upperBound) {
        Random random = new Random();
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = random.nextInt(upperBound - lowerBound) + lowerBound;
        }
        return result;
    }
}

核心原因分析 #

1. 时间复杂度的理论认知偏差 #

你之前对优先队列的时间复杂度描述有误：优先队列实现的实际时间复杂度是O(nlogk)，每次offer和poll操作都需要O(logk)的堆调整时间。当k取n/2时，logk≈log(n/2)，此时O(nlogk)和O(nlogn)的理论差距已经很小，而实际运行中JVM的排序优化会彻底抹平这个差距甚至反超。

2. Arrays.sort的底层优化碾压通用优先队列 #

Java的Arrays.sort(int[])采用双枢轴快速排序，针对基本类型做了极致优化：

• 直接操作原始类型数组，完全避免了优先队列中int转Integer的装箱/拆箱开销——1亿次装箱操作会产生大量临时对象，不仅占用内存，还会触发频繁GC；
• 内存局部性极佳：排序在连续数组内存上进行，CPU缓存命中率极高；而优先队列的二叉堆实现是跳跃式访问元素，缓存命中率低很多；
• 自适应优化策略：针对小数据量自动切换插入排序，控制递归深度避免栈溢出，甚至有汇编级的性能优化。

3. 优先队列的额外运行开销 #

你的优先队列实现还有几个隐性开销：

• 每处理一个元素都可能触发两次堆调整：一次offer的堆化，若队列大小超过k还要再做一次poll的堆化；
• 优先队列的内部数组会动态扩容，扩容时的数组复制操作会增加额外耗时；
• 包装类型的对象创建与回收会给GC带来巨大压力，拖慢整体运行速度。

4. k值的影响放大了差距 #

当k接近n/2时，优先队列需要维护一个大小为n/2的堆，堆调整的开销已经非常大；而排序算法在这种数据规模下，其优化策略（如缓存友好、分支预测）能发挥最大作用。只有当k很小（比如k=10）时，优先队列的优势才会显现。

优化建议 #

如果想提升优先队列实现的性能，可以尝试以下调整：

• 使用原始类型优先队列：自己实现基于int数组的二叉堆，彻底避免装箱拆箱；
• 预先指定优先队列的初始容量：new PriorityQueue<>(k)，避免动态扩容带来的数组复制开销；
• 改用快速选择算法（Quickselect）：这是理论上O(n)的算法，专门针对第k大/小元素的场景，实际性能在大数据量下会远优于优先队列。

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