Java Community | Help. Code. Learn.•7mo ago

Week 73 — What is a `PriorityQueue` and how does it differ from regular `Queue`s?

Question of the Week #73

What is a PriorityQueue and how does it differ from regular Queues?

6 Replies

A Queue typically allows elements to be inserted and retrieved in the order of insertion.

Queue<Integer> queue = new ArrayDeque<>();
queue.add(10);
queue.add(100);
queue.add(50);
System.out.println(queue.poll());//10
//using peek(), we can get the element that would be returned next
System.out.println(queue.peek());//100
System.out.println(queue.poll());//100
System.out.println(queue.poll());//50

Queue<Integer> queue = new ArrayDeque<>();
queue.add(10);
queue.add(100);
queue.add(50);
System.out.println(queue.poll());//10
//using peek(), we can get the element that would be returned next
System.out.println(queue.peek());//100
System.out.println(queue.poll());//100
System.out.println(queue.poll());//50

On the other hand, a PriorityQueue allows inserting elements and then always retrieving the smallest element.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(100);
priorityQueue.add(50);
System.out.println(priorityQueue.poll());//10
//we can also look at the head (smallest element) without removing it
System.out.println(priorityQueue.peek());//50
System.out.println(priorityQueue.poll());//50
System.out.println(priorityQueue.poll());//100

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(100);
priorityQueue.add(50);
System.out.println(priorityQueue.poll());//10
//we can also look at the head (smallest element) without removing it
System.out.println(priorityQueue.peek());//50
System.out.println(priorityQueue.poll());//50
System.out.println(priorityQueue.poll());//100

However, it should be noted that the elements in a PriorityQueue are not sorted. While it ensures that polling/removing the head always accesses the smallest element, iterating over all elements may not result in the elements being sorted. In fact, PriorityQueue does not have any guaranteed iteration order. Retrieving the elements of a PriorityQueue in order requires removing them one after each other.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(100);
priorityQueue.add(50);
priorityQueue.add(75);
//the order of elements is not specified here
System.out.println(priorityQueue);//[10, 75, 50, 100]

//if we remove all elements, we get them in order
//10
//50
//75
//100
while(!priorityQueue.isEmpty()) {
  System.out.println(priorityQueue.poll());
}

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(100);
priorityQueue.add(50);
priorityQueue.add(75);
//the order of elements is not specified here
System.out.println(priorityQueue);//[10, 75, 50, 100]

//if we remove all elements, we get them in order
//10
//50
//75
//100
while(!priorityQueue.isEmpty()) {
  System.out.println(priorityQueue.poll());
}

Internally, PriorityQueue uses an array-based MinHeap.

📖 Sample answer from dan1st

Eric McIntyre•7mo ago

PriorityQueue is a kind of queue where the rule of element being dequeue is determined by the maximum or minimum priority value each element has. Different from regular queue, which the element being dequeue is based on FIFO (First-In-First-Out) characteristic.

Submission from .brutallus

Eric McIntyre•7mo ago

hello , pq is an ordered containersorts ur data in ascending and if u want descending order insertion and removal takes O(logn ) of time queue is a container with unordered data the top of pq is the element with the highest value or lowest value depending on ur implementation while queue is the first inserted element

Submission from gonzothegovernment

Eric McIntyre•7mo ago

Priority Queue are the queue which are serve basis on their priority, means if the data is entered in queue then they can be be accesed according to their priority not sequence number. In priority queue a priority number has been set while entering the data.

Submission from chandrashekhar_

Eric McIntyre•7mo ago

A priority Queue in Java is a data structure that orders it's elements according to their priority, with the highest-priority element always at the front of the queue. It is implemented using a heap data structure. On the other hand, a regular Queue in Java follows the First-In-First-Out (FIFO) principle, where the first element added to the queue is the first one to be removed.

Submission from techstack_joyel

Eric McIntyre•7mo ago

Normal Queue which obeys the rule that the order in which consumers take element from the queues is the same as producers produces element into it(FIFO, such as LinkedBlockingQueue/ArrayBlockingQueue). It is impossible for a producer to cut in line(based on priority) while producing elements, However, PriorityQueue can easily do this, we can specify a priority(usually ranging from 1 to 10) for elements as they sent. In this way, the consumer can automaticlly take the highest priority elements.

public class Main {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.enqueue("Task 1", 3); // priority 3
        pq.enqueue("Task 2", 1); // priority 1
        pq.enqueue("Task 3", 2); // priority 2

        // ordered elements should be Task 2 -> Task 3 -> Task 1
        System.out.println(pq.dequeue()); // print Task 2
        System.out.println(pq.dequeue()); // print Task 3
        System.out.println(pq.dequeue()); // print Task 1
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.enqueue("Task 1", 3); // priority 3
        pq.enqueue("Task 2", 1); // priority 1
        pq.enqueue("Task 3", 2); // priority 2

        // ordered elements should be Task 2 -> Task 3 -> Task 1
        System.out.println(pq.dequeue()); // print Task 2
        System.out.println(pq.dequeue()); // print Task 3
        System.out.println(pq.dequeue()); // print Task 1
    }
}

Submission from wzq1008

Gaming

Programming

Week 73 — What is a `PriorityQueue` and how does it differ from regular `Queue`s?