时间戳

首页 > 解决方案 > 如何从列表/集合和自定义比较器在 Java 中以 O(N) 创建优先级队列

java - 如何从列表/集合和自定义比较器在 Java 中以 O(N) 创建优先级队列

问题描述

我想使用自定义比较器从 ArrayList 创建一个优先级队列。

public PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator))

但是PriorityQueue中没有这样的构造函数

我可以看到这些构造函数，但还没有找到一种在 O(n) 中做到这一点的方法，就像heapify()我会做的那样。

  1. 首先使用构造函数创建一个 PQ，然后使用addAll(...). addAll()将是 O(nlogn) 因为addAll()内部调用add()输入集合的每个元素。
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList.size(), comparator);
priorityQueue.addAll(inputList);
  1. 通过 Collection 构造函数创建 PQ：它没有设置比较器的方法
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList);

标签： javaheappriority-queue

解决方案

一种方法是子类化PriorityQueue并添加所需的构造函数。然后将集合数组的副本存储在子类中并覆盖PriorityQueue#toArray以返回存储的集合的数组。最后，PriorityQueue使用PriorityQueue(PriorityQueue<> pq)构造函数构造一个最终调用的构造函数PriorityQueue#heapify，它使用PriorityQueue#siftDown而不是PriorityQueue#siftUp。这将实现O(N)您想要的复杂性。

这是一个使用构建器类封装（隐藏）子类的示例实现PriorityQueue：

/**
 * Builder class used to create a {@code PriorityQueue<E>} from a
 * {@code Collection<? extends E>} and a {@code Comparator<? super E>} in
 * {@code O(N)} time.
 * 
 * @see PriorityQueueBuilder#build(Collection, Comparator)
 */
public final class PriorityQueueBuilder {
    
    /** Don't subclass this class. */
    private PriorityQueueBuilder() {}
    
    /**
     * Creates a priority queue using a specified collection and comparator in
     * {@code O(N)} time.
     * 
     * @param <E> - the priority queue's type
     * @param c - the collection to create the priority queue with
     * @param comparator - the comparator to be used by the priority queue
     * @return a priority queue created from the specified collection and
     *         comparator
     * @throws NullPointerException if the specified collection is {@code null}
     */
    public static <E> PriorityQueue<E> build(Collection<? extends E> c, Comparator<? super E> comparator) {
        return new PriorityQueue<>(new NPriorityQueue<>(c, comparator));
    }
    
    
    /**
     * Temporary priority queue implementation used to create an actual
     * {@code PriorityQueue<E>}.
     * 
     * We extend {@code PriorityQueue} in order to use the 
     * {@code PriorityQueue(PriorityQueue<? extends E> pq)} constructor rather 
     * than its {@code PriorityQueue(Collection<? extends E> c)} constructor
     */
    private static class NPriorityQueue<E> extends PriorityQueue<E> {
        
        private Object[] nQueue;
        
        /**
         * Sets the comparator and makes a copy of the collections underlying
         * object array.
         */
        public NPriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator) {
            super(comparator);
            
            nQueue = c.toArray();
        }
        
    

       /**
         * Returns an array containing all of the elements in this queue.
         * The elements are in no particular order.
         * 
         * We need to override this method in order to return our
         * {@code nQueue} rather than {@code PriorityQueue}'s
         * {@code queue}. {@code PriorityQueue} calls this method to construct
         * the queue in {@code initElementsFromCollection}.
         *
         * @return an array containing all of the elements in this queue
         */
        @Override
        public Object[] toArray() {
            // no need to return a copy, just pass along the reference
            return nQueue;
        }
        
    }
    
}

这是一个测试上述方法的类：

public class Driver {
    
    public static final int RANGE_START = 1;
    public static final int RANGE_END = 10;
    
    /**
     * Entry point of the program.
     * @param args - command line arguments
     */
    public static void main(String[] args) {
        List<Integer> list = IntStream.rangeClosed(RANGE_START, RANGE_END)
                .boxed()
                .collect(Collectors.toList());
        
        Collections.shuffle(list);
        
        PriorityQueue<Integer> pq = PriorityQueueBuilder.build(list, getComparator());
        
        outputList(list);
        outputPriorityQueue(pq);
    }
    
    private static Comparator<Integer> getComparator() {
        return new Comparator<Integer>()
        {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        };
    }
    
    private static void outputList(List<?> l) {
        System.out.print("         List: ");
        l.forEach(e -> System.out.printf("%2d ", e));
        System.out.println();
    }
    
    private static void outputPriorityQueue(PriorityQueue<?> pq) {
        System.out.print("PriorityQueue: ");
        while (!pq.isEmpty()) {
            System.out.printf("%2d ", pq.poll());
        }
        System.out.println();
    }
    
}

这是运行测试类的输出：

         List:  4  8  3  7 10  2  9  5  6  1 
PriorityQueue:  1  2  3  4  5  6  7  8  9 10

推荐阅读