Java PriorityQueue自定义Comparator对比String数组排序问题排查

需求说明 #

需要实现一个PriorityQueue，将入队的String元素与指定String数组对比排序：数组内的元素优先级高于数组外的元素，数组内的元素期望按数组中的顺序排列，数组外的元素顺序无特殊要求。

代码与问题重现 #

主类代码 #

public class App 
{
    public static void main( String[] args )
    {
        PriorityString priorityString = new PriorityString();
        
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(priorityString);
        
        priorityQueue.add("test");
        priorityQueue.add("john");
        priorityQueue.add("blue");
        priorityQueue.add("orange");
        priorityQueue.add("grape");
        priorityQueue.add("handle");
        
        while (!priorityQueue.isEmpty()) {
            System.out.println("Removed: " + priorityQueue.remove());
        } 
    }
}

初始Comparator实现 #

import java.util.Arrays;
import java.util.Comparator;

public class PriorityString implements Comparator<String> {
    
    String[] valueStrings;
    
    PriorityString() {
        valueStrings = new String[] {"all", "john", "door", "floor", "record", "desk", "orange"};
    }

    @Override
    public int compare(String o1, String o2) {
        if (Arrays.asList(valueStrings).contains(o1))
            return 0;
        else
            return 1;
    }
}

初始结果

Removed: test
Removed: john
Removed: orange
Removed: blue
Removed: handle
Removed: grape

问题：不在数组中的test始终排在首位，数组内元素的优先级没有正确体现。

第一次修改后的Comparator #

@Override
public int compare(String o1, String o2) {
    if (Arrays.asList(valueStrings).contains(o1))
        return -1;
    else if (Arrays.asList(valueStrings).contains(o2)) 
        return 0;
    else
        return 1;
}

修改后结果

Removed: orange
Removed: handle
Removed: grape
Removed: test
Removed: blue
Removed: john

问题：数组内的john被排到末尾，不符合“数组内元素优先级更高”的预期。

调整后的最终Comparator #

@Override
public int compare(String o1, String o2) {
    if (Arrays.asList(valueStrings).contains(o1))
        return -1;
    else if (Arrays.asList(valueStrings).contains(o2)) 
        return 1;
    else
        return 0;
}

调整后结果

Removed: orange
Removed: john
Removed: grape
Removed: test
Removed: blue
Removed: handle

问题根源分析 #

Java的PriorityQueue基于堆结构实现，其正确工作的核心依赖于Comparator必须严格遵守比较契约：

1. 自反性：compare(a,a)必须返回0；
2. 对称性：若compare(a,b)=x，则compare(b,a)必须返回-x；
3. 传递性：若compare(a,b)<0且compare(b,c)<0，则compare(a,c)<0。

初始实现的问题 #

初始compare方法逻辑完全违反契约：

• 当o1在数组中、o2不在时，compare(o1,o2)=0，但compare(o2,o1)=1，破坏了对称性；
• 传递性也无法满足：比如compare(john,test)=0，compare(test,blue)=1，但compare(john,blue)=0，不符合传递性。
  这种错误的比较逻辑导致堆无法正确构建，出现了“不在数组的元素反而排在堆顶”的异常结果。

第一次修改的问题 #

修改后的逻辑中，当o1不在数组但o2在数组时，返回0，错误地将“数组内元素”和“数组外元素”视为优先级相等，导致堆不会将数组内的john调整到更高优先级位置，最终被排到末尾。

当前实现的正确性验证 #

当前的实现满足“数组内元素优先级高于数组外元素”的核心需求，但仍存在缺陷：

• 当两个元素都在数组中时，compare(o1,o2)始终返回-1，意味着任何数组内的元素都被认为比另一个数组内元素优先级更高，这完全违反了对称性和传递性；
• 这种情况下，数组内元素的输出顺序是不确定的（比如测试结果中orange先于john输出，但按数组顺序john应该更靠前），堆的行为会变得不可预测。

更完善的实现 #

如果需要数组内的元素按照数组中的索引顺序排序（索引越小优先级越高），可以优化Comparator如下：

import java.util.Arrays;
import java.util.Comparator;

public class PriorityString implements Comparator<String> {
    
    String[] valueStrings;
    
    PriorityString() {
        valueStrings = new String[] {"all", "john", "door", "floor", "record", "desk", "orange"};
    }

    @Override
    public int compare(String o1, String o2) {
        boolean o1InArray = Arrays.asList(valueStrings).contains(o1);
        boolean o2InArray = Arrays.asList(valueStrings).contains(o2);
        
        if (o1InArray && o2InArray) {
            // 按数组中的索引顺序排序，索引小的优先级高
            int idx1 = Arrays.asList(valueStrings).indexOf(o1);
            int idx2 = Arrays.asList(valueStrings).indexOf(o2);
            return Integer.compare(idx1, idx2);
        } else if (o1InArray) {
            // o1在数组，优先级更高
            return -1;
        } else if (o2InArray) {
            // o2在数组，优先级更高
            return 1;
        } else {
            // 都不在数组，按自然顺序排序（或返回0）
            return o1.compareTo(o2);
        }
    }
}

这个实现严格遵守比较契约，能保证：

1. 数组内元素按数组索引顺序优先输出；
2. 数组内元素优先级始终高于数组外元素；
3. 数组外元素按自然顺序排序（可根据需求调整）。

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