How does Java's PriorityQueue differ from a min-heap?

java priority-queue
Jeff Chen picture Jeff Chen · May 20, 2011 · Viewed 97k times · Source

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?

Answer

spiralmoon picture spiralmoon · Dec 13, 2013

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

Related questions

How do I use a PriorityQueue?

How do I get a PriorityQueue to sort on what I want it to sort on? Also, is there a difference between the offer and add methods?

Read More
Change priorityQueue to max priorityqueue

I have priority queue in Java of Integers: PriorityQueue<Integer> pq= new PriorityQueue<Integer>(); When I call pq.poll() I get the minimum element. Question: how to change the code to get the maximum element?

Read More
Updating Java PriorityQueue when its elements change priority

I'm trying to use a PriorityQueue to order objects using a Comparator. This can be achieved easily, but the objects class variables (with which the comparator calculates priority) may change after the initial insertion. Most people have suggested the simple …

Read More