如何配置Java优先级队列以忽略重复项？

Question

我认为add()应该忽略重复,但我的输出有重复.我怎么不存储重复？

我还想知道优先级队列如何检查两个元素是否重复.我猜它正在使用比较器等于,但我只想确定.

谢谢

Answer 1

以下是PriorityQueue Javadoc的一部分:

此队列根据构造时指定的顺序对元素进行排序,该顺序根据其自然顺序(请参阅Comparable)或根据比较器指定,具体取决于使用的构造函数.

所以,是的,PriorityQueue使用Comparator(如果您将其指定为构造函数参数)或使用compareTo(...)方法(元素必须实现Comparable接口).

PriorityQueue允许重复.因此,如果您想避免这种情况,则需要实现自己的Queue版本.你可以找到非常优雅的方法,如何在"Effective Java",第85页中做到这一点.或者,您可以扩展PriorityQueue类并覆盖add方法(这是放置contains(...)检查的理想位置).

Answer 2

PriorityQueueJava中的A 对重复元素没有任何限制.如果要确保优先级队列中永远不会出现两个相同的项目,那么最简单的方法是Set与优先级队列并行维护.每次要将元素插入优先级队列时,您可以检查该集合是否已包含该元素,如果没有,则将其添加到集合和优先级队列中.每当从优先级队列中删除元素时,只需从集合中删除该元素.

或者,根据您打算在优先级队列上执行哪些操作,以及如何在您的情况下定义相等性,将其替换为单个可能是可行的,TreeSet因为这仍然允许您执行您将拥有的所有重要操作访问优先级队列,同时另外不允许重复.

Answer 3

import java.util.PriorityQueue;

public class NoDuplicates<E> extends PriorityQueue<E> 
{
    @Override
    public boolean offer(E e) 
    {
        boolean isAdded = false;
        if(!super.contains(e))
        {
            isAdded = super.offer(e);
        }
        return isAdded;
    }
    public static void main(String args[])
    {
        PriorityQueue<Integer> p = new NoDuplicates<Integer>();
        p.add(10);
        p.add(20);
        p.add(10);
        for(int i =0;i<=2;i++)
        {
            System.out.println(p.poll());
        }

    }
}