如何在线性时间内构建具有自定义比较器的优先队列

Question

如何在线性时间内构建具有自定义比较器的优先队列

javaperformanceheappriority-queue

7

在PriorityQueue的构造函数中，我们可以传递像List或Set这样的集合，以线性时间构建PriorityQueue。但是，这也意味着PriorityQueue将使用默认比较器。

我想使用自己的比较器，这样我就可以拥有不同于最小堆的东西。我能想到的唯一方法是将集合包装在SortedSet中，并在其中放置一个定制的比较器。

还有其他更好的方法吗？

- Bubblespot

创建一个PriorityQueue的子类，并覆盖默认的比较器？ - Scott Hunter

1

@ScottHunter PriorityQueue类中的所有字段和方法都不是受保护的，因此子类无法覆盖它们。 - Bubblespot

不，没有；这个功能被省略在PriorityQueue中。没有办法做你想要的事情。 - Louis Wasserman

4个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexander Anikin · Answer 1

创建包含数据对象并实现Comparable接口的代理类。创建此类对象的列表，将其传递给PriorityQueue构造函数。

我不知道有哪些有效的SortedSet实现可以保证可比较对象的创建时间为O(n)。虽然可以针对基数友好键在O(n)内对数组进行排序（实际上，线性排序在一般情况下往往不太快），因此您可以制作具有快速创建功能的自定义SortedSet，以与您的特殊比较器兼容。

仅对可比较对象进行堆构造可以在O(n)内完成，因为它不会完全对列表进行排序。

- maaartinus · Answer 2

在PriorityQueue的构造函数中，我们可以传入像List或Set这样的集合，以线性时间构建PriorityQueue。

但是，这也意味着PriorityQueue将使用默认的比较器。

不正确。

javadoc中提到：

如果指定的集合是一个SortedSet实例或另一个PriorityQueue，则此优先级队列将按照相同的顺序排序。

因此，当从已知的排序集合开始时，您可以获得其Comparator。此外，您可以在线性时间内完成。

否则，您就不能。source清楚地展示了这一点（查找heapify()）。

如果您有一个未排序的列表，则无法在线性时间内获取优先级队列（除非优先级队列懒惰地确保堆属性；但那是作弊）。

- Nicolas Alba Murillo · Answer 3

我有同样的问题。

我认为唯一的解决方法是创建一个包装类，该类包含一个对象T并实现Comparable接口，如下所示：

class ModifiedPriorityQueue<T> extends PriorityQueue<Wrapper<T>> {

    public ModifiedPriorityQueue(Collection<T> collection, Comparator<T> comparator) {
        super(collection.stream().map(x -> new Wrapper<>(x, comparator)).collect(Collectors.toList()));
    }
}

class Wrapper<T> implements Comparable<Wrapper<T>> {

    private final T object;
    private Comparator<T> comparator;

    public Wrapper(T object, Comparator<T> comparator) {
        this.object = object;
        this.comparator = comparator;
    }

    @Override
    public int compareTo(Wrapper<T> o) {
        return comparator.compare(object, o.object);
    }

    @Override
    public String toString() {
        return object.toString();
    }
}

class Main {
    public static void main(String[] args) {
        Collection<Integer> elements = Arrays.asList(1, 2, 3, 4);
        ModifiedPriorityQueue<Integer> p = new ModifiedPriorityQueue<>(elements, Comparator.reverseOrder());

        while (!p.isEmpty()) {
            System.out.println(p.poll());
        }
    }
}

- Sergey Benner · Answer 4

假设您有一个名为A的类（或POJO），其中包含一个int类型的priority字段，该字段保存了此对象的优先级以及其getter方法getPriority()。然后您可以像下面这样使用它：

 Queue<A> queue = new PriorityQueue<>(
                    4 //initialCapacity
                 , new Comparator<A>() {
                public int compare(A p1, A p2) {
                    return Integer.valueOf(p1.getPriority()).compareTo(p2.getPriority());
                }
            });