Why did they name PriorityQueue
if you can't insertWithPriority? It seems very similar to a heap. Are there any differences? If no difference, then why was it named PriorityQueue
and not Heap?
7 Answers
The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
In order to implement a max-heap, you can create your own Comparator:
import java.util.Comparator;
public class MyComparator implements Comparator<Integer>
{
public int compare( Integer x, Integer y )
{
return y - x;
}
}
So, you can create a min-heap and max-heap in the following way:
PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());
-
4
-
2@ThinkRecursively doing a
minus
to get a reverse comparator is a terrible idea– EugeneOct 2, 2018 at 19:55 -
7
-
2Using
y - x
as a comparator is broken, as it can overflow. The safe solutionCollections.reverseOrder()
exists since Java 1.2.– HolgerMar 13, 2019 at 8:30 -
4@Neil when you use Java 8, you can use
new PriorityQueue<>(Collections.reverseOrder())
(use the “diamond operator”).– HolgerMar 13, 2019 at 8:31
For max-heap you can use:
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
-
14
Add() works like an insertWithPriority.
You can define priority for the type that you want using the constructor:
PriorityQueue(int, java.util.Comparator)
look under https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html
The order the Comparator gives will represent the priority in the queue.
Default behaviour as described in other answers
Min Heap(Default):
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
For Max Heap:
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2-o1);
From the PriorityQueue
JavaDocs:
An unbounded priority queue based on a priority heap. 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.
Priority is meant to be an inherent property of the objects in the queue. The elements are ordered based on some sort of comparison. To insert some object with a given priority, you would just set whatever field(s) on the object affect the ordering, and add()
it.
And, as @Daniel commented,
Generally Java Objects are named based on the functionality they provide, not named based on how they are implemented.
From Java docs
Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering.
Here is a working code for maxHeap and minHeap using PriorityQueue
-
class HeapDemo {
private final static int HEAP_SIZE = 10; //size of heap
//INNER CLASS
static class maxHeapComparator implements Comparator<Integer> {
@Override
public int compare (Integer x, Integer y) {
return y-x; //reverse order
}
}
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE, new maxHeapComparator());
for(int i=1; i<=HeapDemo.HEAP_SIZE; ++i){
int data = new Random().nextInt(100) +1; //number between 0 to 100
minHeap.add(data);
maxHeap.add(data);
}
System.out.print("\nMIN Heap : ");
Iterator<Integer> iter = minHeap.iterator();
while(iter.hasNext()){
System.out.print(iter.next() + " ");
}
System.out.print("\nMAX Heap : ");
iter = maxHeap.iterator();
while(iter.hasNext()) {
System.out.print(iter.next() + " ");
}
}
}
sample o/p :
MIN Heap : 20 32 37 41 53 91 41 98 47 86
MAX Heap : 98 91 41 53 86 20 37 41 32 47
-
As with all other answers, using
y - x
as a comparator is broken, as it can overflow. The safe solutionCollections.reverseOrder()
exists since Java 1.2.– HolgerMar 13, 2019 at 8:33
From http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time
for integer, long, float, double, character, boolean (i.e. primitive data types) the natural ordering is ascending order, that's why Arrays.sort(arr) {where arr is an array of primitive data type} sorts the value of arr in ascending order. You can change the natural ordering by using a Comparator
Comparator can be used in two ways either
One of the way is how DpGeek showed
Another way is by using Anonymous Class. For example
Arrays.sort(arr, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
return y - x;
}
});
- If you have java8 then you can use the lambda expression
Arrays.sort(arr, (Integer x, Integer y) -> y - x);
This sorts the array arr in descending order
min-heap
andmax-heap
are bothpriority queue
, it depends on how you define the order of priority. That is to say, a priority queue can be a min-heap or a max-heap in your algorithm.