Providing a comparator and collection to PriorityQueue

Question

I have a Map<Integer,Integer> freqMap where each value is the frequency of the key Now I want to build a priorityQueue from this map

I was expecting a constructor like PriorityQueue pq = new PriorityQueue(freqMap.keySet(), comparator); But there is no such constructor. Although I can construct it using a comparator and then add the keySet elements using addAll But that will internally add elements one by one. In case I want to build a max heap out of the key set with comparator as the values. I am not sure how can I do this.

My Thoughts:
one way could be that instead of Integer I make a custom class and wrap those integers and make the class implement a Comparable interface. Then when I pass that collection as a parameter to the priorityQueue constructor it should construct the priority Queue in O(n) time.
Whereas if I use the addAll method then probably it will take O(n log n) time. I am not sure though if my reasoning is correct here. It does seem a little complicated to just use a wrapper class that implements comparable for this tiny purpose.
The comparable will compare based on values so the key with the highest value should be on top.

Answer 1

construct the priority Queue in O(n) time

The only case when you can construct a new PriorityQueue in a linear time O(n) is when you already have another PriorityQueue.

In such case, the copy-constructor internally would invoke method initFromPriorityQueue() which would create a copy of the underlying array of the given PriorityQueue and would assign this copy to the underlying array of this (newly created) queue. The copying of elements would cost O(n).

But when you have a collection that is not a PriorityQueue there's no way to ensure that the elements are ordered as required. That means that you need to enqueue them one-by-one, there's no workaround. For each element, it would have a cost of O(log n). And the overall time complexity would be linear-logarithmic O(n log n).

Here's a quote from the documentation regarding the time complexity of operations:

Implementation note:

this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add);

Since a Binary Heap (PriorityQueue is an implementation of the Binary Heap data structure) has the worst case time complexity O(log n) for inserting a new element, then inserting n would run in linear-logarithmic time.

Regarding the mechanism behind addAll(), as in many other collections it delegates to the method add() which a logarithmic worst case time complexity (see the implementation note quoted above).

Note

• All the information provided above is relevant for the PriorityQueue class from the JDK, which is implemented as a Binary Heap (don't confuse this class with the Priority queue data structure).

• There are many ways to implement Heap data structure. And some of them like Fibonacci Heap have amortized O(1) time complexity for insertion, which allows populating them with n elements in linear time O(n). In such implementation would be included in the JDK in the future, then almost certainly it would not replace the current PriorityQueue implementation, but rather would be introduced as a new class (that's how Java is being developed since it's earlier days: new things come, almost nothing goes away).