How does Java's PriorityQueue differ from a min-heap?
JavaPriority QueueJava Problem Overview
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?
Java Solutions
Solution 1 - Java
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());
Solution 2 - Java
For max-heap you can use:
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
Solution 3 - Java
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.
Solution 4 - Java
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.
Solution 5 - Java
From Java docs
> Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+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
Solution 6 - Java
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
Solution 7 - Java
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);