82

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?

4
  • 18
    I'm not sure if it differs from a min-heap, but generally Java Objects are named based on the functionality they provide, not named based on how they are implemented.
    – Daniel
    May 19, 2011 at 22:54
  • 1
    @Daniel Ok that explains why it's not called a heap, but why is it called a PriorityQueue if it does not support the functionality of a priority queue?
    – Jeff Chen
    May 19, 2011 at 22:58
  • 9
    It does support the functionality of a priority queue.
    – Matt Ball
    May 19, 2011 at 23:04
  • min-heap and max-heap are both priority 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. Nov 2, 2019 at 21:50

7 Answers 7

112

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());
6
  • 4
    exactly it's a min-heap because the default sort order is ascending
    – stivlo
    Jan 22, 2014 at 11:31
  • 2
    @ThinkRecursively doing a minus to get a reverse comparator is a terrible idea
    – Eugene
    Oct 2, 2018 at 19:55
  • 7
    Easier max-heap: Queue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); as since 1.8, you can just pass in the Comparator without needing to pass in the initial capacity.
    – Neil P.
    Mar 4, 2019 at 16:39
  • 2
    Using y - x as a comparator is broken, as it can overflow. The safe solution Collections.reverseOrder() exists since Java 1.2.
    – Holger
    Mar 13, 2019 at 8:30
  • 4
    @Neil when you use Java 8, you can use new PriorityQueue<>(Collections.reverseOrder()) (use the “diamond operator”).
    – Holger
    Mar 13, 2019 at 8:31
61

For max-heap you can use:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
1
  • 14
    Since 1.8, you can just pass in the Comparator without needing to pass in the initial capacity: Queue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
    – Neil P.
    Mar 4, 2019 at 16:38
35

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.

9

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

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.

6

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 
1
  • As with all other answers, using y - x as a comparator is broken, as it can overflow. The safe solution Collections.reverseOrder() exists since Java 1.2.
    – Holger
    Mar 13, 2019 at 8:33
3

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

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

2
  • 3
    Using y - x as a comparator is broken, as it can overflow. The safe solution Collections.reverseOrder() exists since Java 1.2.
    – Holger
    Mar 13, 2019 at 8:32
  • @Holger, excellent point about overlfow. worth adding to SonarCube rules
    – Vortex
    Jan 27, 2022 at 18:54

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.