使用PriorityQueue（Java）进行字符串排序的问题

Question

我试图使用PriorityQueue对字符串列表进行排序并删除重复项。最初我使用PriorityQueue，它不会更改顺序。我换了树集后，它起作用了。但是，我想了解优先级队列和定义比较器的问题是什么。想听听解释。

public class RemoveDuplicateStrings {
    public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }
        return new ArrayList<String>(pq);
    }

    public static void main(String[] args) {
        List<String> output = removeDuplicates(List.of("Hey", "Hi", "Hello", "Hey", "Hello"));
        System.out.println(output);
    }
}

Answer 1

您正在使用ArrayList构造函数，该构造函数从作为参数传递的集合中复制元素，并对其调用ToArray方法。对于priorityqueue，它只是创建底层数组的副本，这些元素没有特定的顺序。从PriorityQueue::ToArray文档：

返回包含此队列中所有元素的数组。这些元素没有特定的顺序。

但是，对于TreeSet::ToArray（从AbstractCollection继承的实现）：

这就是为什么你会得到这样的结果。要获得所需的内容，您必须轮询队列以按照比较器定义的顺序接收元素：

public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }

        ArrayList<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        return result;
}

这里的关键是priorityqueue的迭代器不按实际顺序返回元素，但是对于treeset的顺序是升序的（考虑到比较器）。