如何基于Map<Integer,Integer>高效构建指定规则的PriorityQueue？

方案1：极简实现（O(n log n)时间） #

不需要自定义任何类，直接用Lambda表达式定义比较器，再通过addAll批量添加键集合。这种方式代码最简洁，适合数据量不大的场景：

// 构建最大堆：频率越高的键越靠近堆顶
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    (k1, k2) -> freqMap.get(k2) - freqMap.get(k1)
);
maxHeap.addAll(freqMap.keySet());

时间复杂度说明：addAll底层是逐个调用add方法，每次add需要调整堆结构，时间复杂度为O(log n)，n为键的总数，因此总时间是O(n log n)。

方案2：O(n)时间的高效实现（Java 16+） #

如果追求O(n)的构造时间，又不想写繁琐的自定义类，可以用Java 16引入的record特性，一键包装键和频率并实现比较逻辑：

// 用Record简洁包装键和频率，实现倒序比较（频率高的排前）
record KeyFreq(int key, int freq) implements Comparable<KeyFreq> {
    @Override
    public int compareTo(KeyFreq other) {
        return Integer.compare(other.freq, this.freq);
    }
}

// 把Map的键值对转成KeyFreq集合
List<KeyFreq> keyFreqList = freqMap.entrySet().stream()
    .map(entry -> new KeyFreq(entry.getKey(), entry.getValue()))
    .toList();

// 直接传入集合构造PriorityQueue，底层会执行heapify操作，时间复杂度O(n)
PriorityQueue<KeyFreq> maxHeap = new PriorityQueue<>(keyFreqList);

// 后续取堆顶元素时，只需调用key()方法获取原键
// Integer topKey = maxHeap.poll().key();

时间复杂度说明：PriorityQueue的PriorityQueue(Collection<? extends E> c)构造方法会对集合执行heapify（堆化）操作，堆化的时间复杂度是O(n)，比逐个添加高效得多。

方案3：兼容旧Java版本的O(n)实现 #

如果项目还在使用Java 16以下的版本，就需要手动写一个简单的包装类实现Comparable接口，代码量也不算大：

class KeyFreq implements Comparable<KeyFreq> {
    private int key;
    private int freq;

    public KeyFreq(int key, int freq) {
        this.key = key;
        this.freq = freq;
    }

    public int getKey() {
        return key;
    }

    @Override
    public int compareTo(KeyFreq other) {
        // 按频率倒序排列
        return Integer.compare(other.freq, this.freq);
    }
}

// 后续步骤和方案2一致：转集合、构造PriorityQueue
List<KeyFreq> keyFreqList = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
    keyFreqList.add(new KeyFreq(entry.getKey(), entry.getValue()));
}
PriorityQueue<KeyFreq> maxHeap = new PriorityQueue<>(keyFreqList);

关于时间复杂度的验证 #

你之前的推理是正确的：

• 用addAll逐个添加元素：每次添加都要进行堆的上浮调整，总时间O(n log n)
• 传入集合直接构造PriorityQueue：底层通过heapify一次性完成堆结构构建，总时间O(n)

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