优先级队列的字符串排序问题(Java)

Question

我试图使用PriorityQueue对字符串列表进行排序，并删除重复的字符串。最初我使用PriorityQueue，它没有改变顺序。在我改用TreeSet之后，它就工作了。但是，我想了解一下，在定义了比较器的情况下，优先级队列的问题是什么？希望听到一些解释。

没有工作的代码。

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);
    }
}

我得到的结果是： [Hello, Hi, Hey]正确的顺序应该是: hello, hey, hi.

在我将数据结构改为TreeSet，并使用相同的比较器后，它就工作了。

Answer 1

你正在使用 ArrayList 构造者 从作为参数传递的集合中复制元素，然后调用 toArray 方法。对于 PriorityQueue 它只是对底层数组进行复制，而且这些元素没有特定的顺序。从 PriorityQueue::toArray docs :

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

然而对于一个 TreeSet::toArray 继承自 AbstractCollection):

返回一个包含该集合中所有元素的数组。如果这个集合对其迭代器返回元素的顺序做了任何保证，那么这个方法必须以相同的顺序返回元素。

而实际上 TreeSet 对它的迭代器返回的元素顺序进行担保。从 TreeSet::iterator docs :

以升序返回这个集合中元素的迭代器。

这就是为什么你会得到这样的结果。为了得到你想要的结果，你必须对你的队列进行轮询，以比较器定义的顺序来接收元素。

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 不返回元素i的顺序，但是对于 TreeSet 顺序是升序的（考虑到比较器）。