How to create a Priority Queue in O(N) in Java from a list/collection and a custom comparator

user_2455546 0
Viewed 561

I want to create a priority queue from an ArrayList with a custom comparator.

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

BUT there is no such constructor in PriorityQueue

I can see these constructors but haven't found a way to do it in O(n) like a heapify() would've done.

  1. Create a PQ with the constructor first and then add using addAll(...). addAll() would be O(nlogn) because addAll() internally calls add() for each element of the input collection.
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList.size(), comparator);
priorityQueue.addAll(inputList);
  1. Create PQ through Collection constructor: It doesn't have a way to set the comparator
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList);
priority-queue heap java
1 Answers

One approach is to subclass PriorityQueue and add the desired constructor. Then store a copy of the collection's array in the subclass and override PriorityQueue#toArray to return the stored collection's array. Finally, construct a PriorityQueue using the PriorityQueue(PriorityQueue<> pq) constructor which will end up calling PriorityQueue#heapify, which uses PriorityQueue#siftDown rather than PriorityQueue#siftUp. This will achieve the O(N) complexity you want.

Here's an example implementation using a builder class to encapsulate (hide) the PriorityQueue subclass:

/**
 * 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;
        }
        
    }
    
}

Here's a class to test the above approach:

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

Here's the output of running the test class:

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