Java Priority Queue heapify-CodePudding

In general, if I understand correctly, there is a difference of runtime between "heapifying;o(n)" a given list vs adding each individual element; o(lg n). Does java follow this behavior? If not below question may not be valid.

The below example appears to create a "min-heap".

List<Integer> myList = List.of(4,3,10,1);
PriorityQueue<Integer> queue = new PriorityQueue<>(myList);

However, let say if I want to build a "max heap", but the constructor does not let me pass in a collection and comparator together. In this case, is the only to build max heap is via creating a wrapper class that implements comparable?

 class Wrapper implements Comparable<Wrapper> {
 ...
 @Override
 int compareTo(Wrapper o) {// define rule here...}
 }

 List<Integer> val = List.of(5,3,2,10);
 List<Wrapper> wrappedVal = val.stream().map(Wrapper::new).collect(Collectors.toList());

 PriorityQueue<Wrapper> queue = new PriorityQueue<>(wrappedVal);

Note: I understand that it is possible to create priority queue with a comparator, then repeatedly call add.

CodePudding user response：

However, let say if I want to build a "max heap", but the constructor does not let me pass in a collection and comparator together. In this case, is the only to build max heap is via creating a wrapper class that implements comparable?

Yes. This class does not provide a constructor that can pass in a collection and a comparator at the same time. It will use the compareTo method of the collection element, so as you did, you need a Wrapper(But this may seem a little unnecessary?).

repeatedly call add.

You can use PriorityQueue#addAll().

CodePudding user response：

From the java doc:

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at QUEUE CONSTRUCTION TIME, depending on which constructor is used https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

So you have to provide the ordering strategy at the time of building the queue. Let say you are trying to have max-heap (ordered in reverse way), then queue construction will look like below:-

Queue<Integer> queue = new PriorityQueue<>(new YourCustomComparator())

Or if you are just handling integers you can leverage the custom one:

Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

This step is just to create the queue. Now how to add the element? Here you have a variety of method signatures available. Let say you have list available then you can simply pass them to addAll method.

Something like this:

 queue.addAll(List.of(5, 3, 2, 10));