Java Priority Queue
It is a class that implements a priority queue data structure.
It stores elements in a way such that each element has an associated priority and elements with higher priorities are served before elements with lower priorities.
It’s a queue where elements are dequeued based on their priority rather than their arrival time.
PriorityQueue must have elements of the same type, and the elements must be comparable to each other.
This means that either the elements must implement the Comparable interface, or you need to provide a Comparator when constructing the PriorityQueue.
The priority queue in Java is implemented as a binary heap.
Why as a binary heap?
It is efficient to insert and remove elements from the queue.
It is efficient to find the element with the highest priority in the queue.
It is efficient to find all of the elements in the queue with a given priority.
The binary heap implementation of the priority queue in Java is based on the following principles:
The elements of the heap are stored in a tree-like data structure.
Each node in the tree has at most two child nodes.
The parent of each node has a higher priority than both of its child nodes.
The heap is always balanced, which means that the height of the tree is always logarithmic in the number of elements in the queue.
PriorityQueue features
PriorityQueue in Java is not based on the first-in-first-out (FIFO) principle like a regular queue.
Element Ordering: The elements in a priority queue are ordered according to their natural ordering (using their Comparable interface)
or by a comparator provided at queue construction time.
For example, if you create a priority queue of integers, then the elements in the queue will be ordered from smallest to largest.
Insertion and Removal: Elements can be inserted into the priority queue using the offer() method and removed using the poll() method.
The peek() method can be used to retrieve the element at the head without removing it.
Performance: The time complexity for both insertion and removal operations is O(log n), where n is the number of elements in the priority queue.
Here using a PriorityQueue, I entered Marks and optionally, I identified the highest and the lowest value.
package com.priorityqueueexample;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueSimple {
/*
Here using a PriorityQueue, I entered Marks and optionally, I identified the highest and the lowest value.
*/
public static void main(String[] args) {
Queue<Double> marks = new PriorityQueue<>();
// Values are stored in the priority of natural order, low to high
// If you want to print high to low use Queue<Double> marks = new PriorityQueue<>(Collections.reverseOrder());
marks.offer(13.4); // Use offer to add values
marks.offer(55.0);
marks.offer(30.12);
marks.offer(90.00);
// Initialize variables to keep track of highest and lowest marks
double highestMark = Double.MIN_VALUE;
double lowestMark = Double.MAX_VALUE;
while (!marks.isEmpty()) {
// Retrieve and remove the lowest value (the highest priority) from the priority queue
double currentMark = marks.poll();
System.out.println(currentMark);
// Update highest and lowest marks
highestMark = Math.max(highestMark, currentMark);
lowestMark = Math.min(lowestMark, currentMark);
}
// Print messages for the highest and lowest marks
System.out.println("The highest mark is: " + highestMark);
System.out.println("The lowest mark is: " + lowestMark);
}
/*
These lines use the Math.max and Math.min methods to compare the current mark (currentMark) with the current highest mark (highestMark) and lowest mark (lowestMark), respectively. These methods are part of the Math class in Java and are used for basic mathematical operations.
Math.max(a, b) returns the larger of the two values a and b.
Math.min(a, b) returns the smaller of the two values a and b.
In the context of the loop, these lines are updating the highestMark and lowestMark variables based on the marks encountered so far.
*/
}Bit complex coding challenge
I have a playlist of rappers here are there priority Eminem 1, DMX 4, Nas 3, Ice Cube 2 .
so based on the priority can you add a message to playing +<rapper> In order of <priority>
package com.priorityqueueexample;
public class Rapper implements Comparable<Rapper> {
String name;
int priority;
// Constructor for creating Rapper objects with name and priority
public Rapper(String name, int priority) {
this.name = name;
this.priority = priority;
}
// Implementation of the compareTo method from the Comparable interface
@Override
public int compareTo(Rapper otherRapper) {
// Compare Rapper objects based on their priority
return Integer.compare(this.priority, otherRapper.priority);
}
}The class with the main method.
package com.priorityqueueexample;
import java.util.PriorityQueue;
public class RapperPriorityQueueExample {
public static void main(String[] args) {
// Creating a priority queue with natural ordering based on Comparable
PriorityQueue<Rapper> rapperPriorityQueue = new PriorityQueue<>();
// Adding rappers to the priority queue based on the priority 1 to 4
rapperPriorityQueue.offer(new Rapper("Eminem", 1));
rapperPriorityQueue.offer(new Rapper("Ice Cube", 2));
rapperPriorityQueue.offer(new Rapper("Nas", 4));
rapperPriorityQueue.offer(new Rapper("DMX", 3));
System.out.println("The size= "+rapperPriorityQueue.size());
// Playing rappers in order of priority
while (!rapperPriorityQueue.isEmpty()) {
// Retrieve and print the rapper with the highest priority
Rapper currentRapper = rapperPriorityQueue.poll();
System.out.println("Playing " + currentRapper.name + " in order of priority " + currentRapper.priority);
}
}
}This will give below output.
Playing Eminem in order of priority 1
Playing Ice Cube in order of priority 2
Playing DMX in order of priority 3
Playing Nas in order of priority 4
