PriorityQueue自定义排序异常：高频优先、同频字典序小规则未生效

你的自定义排序逻辑存在理解偏差，导致PriorityQueue的输出不符合预期。Java的PriorityQueue基于小顶堆实现，堆顶始终是Comparator定义的“最小”元素。你的需求是优先取出频率最高的单词，频率相同时取字典序最小的，因此需要调整Comparator逻辑，确保：

1. 频率更高的元素被视为“更小”的元素（成为堆顶）
2. 频率相同时，字典序更小的元素被视为“更小”的元素

错误原因 #

你当前的compare方法中，频率比较的逻辑看似正确，但实际运行异常大概率是代码存在笔误（比如误将b.freq - a.freq写成a.freq - b.freq），或是对PriorityQueue的特性理解有误——它仅保证堆顶是最小元素，内部元素并非完全有序，但poll()操作会严格按照优先级依次取出元素。

修正后的代码 #

以下是符合需求的正确实现：

import java.util.*;

class Pair {
    String word;
    int freq;

    Pair(String word, int frequency) {
        this.word = word;
        this.freq = frequency;
    }
}

class SortCustom implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        // 按频率降序：频率高的元素被视为"更小"，优先出堆
        int freqCompare = Integer.compare(b.freq, a.freq);
        if (freqCompare != 0) {
            return freqCompare;
        }
        // 频率相同时按字典序升序：字典序小的元素优先出堆
        return a.word.compareTo(b.word);
    }
}

public class HelloWorld {
    public static void main(String[] args) {
        PriorityQueue<Pair> queue = new PriorityQueue<>(new SortCustom());
        queue.add(new Pair("leaf",1));
        queue.add(new Pair("i",2));
        queue.add(new Pair("love",2));
        queue.add(new Pair("code",1));
        while(!queue.isEmpty()){
            System.out.println(queue.poll().word);
        }
    }
}

输出结果 #

运行后将得到你期望的输出：

i
love
code
leaf

关键说明 #

• 用Integer.compare(b.freq, a.freq)替代直接减法，避免整数溢出风险，同时更符合规范。
• 频率相同时，a.word.compareTo(b.word)返回负数意味着a的字典序更小，会被视为“更小”元素优先出堆。

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