DEV Community

loizenai
loizenai

Posted on

How to use Java PriorityQueue with Examples

https://grokonez.com/java/how-to-use-java-priorityqueue-with-examples

[no_toc]In the tutorial, Grokonez introduces how to work with Java PriorityQueue by examples:

  • How does Java PriorityQueue work?
  • Explore Java PriorityQueue Hierarchy
  • Create Java PriorityQueue with Integer, String, and Custom Object Class

Related posts:

Java PriorityQueue

  • Java PriorityQueue is an unbounded priority queue.
  • The elements of the priority queue are ordered according to their natural ordering, or by a Comparator.
    • The front of the priority queue contains the least element.
    • And the rear of the priority queue contains the greatest element.

grokonez-howto-java-priority-queue-examples

  • PriorityQueue does not permit null elements.
  • PriorityQueue does not permit insertion of non-comparable objects. ClassCastException will be throwed.
  • The head of this queue is the least element. The queue operations poll, remove, peek, and element access the element at the head of the queue.
  • Java PriorityQueue is not synchronized. Multiple threads should not access the same PriorityQueue concurrently if having any of the threads modifies the queue.

    Java PriorityQueue Hierarchy

grokonez-java-priority-queue-hierarchy-examples

Java PriorityQueue with Integer Example

In the follwing example, We create an Integer Java PriorityQueue, then do a list operations on the queue:

  • Insert an element to PriorityQueue with offer and add method.
  • Retrieve a head value of the Queue, but NOT remove it by peek() method.
  • Removes a single instance of the specified element from this queue by remove(Object o) method.
  • Retrieves and removes the head of this queue by poll() method.

Example:


import java.util.PriorityQueue;
import java.util.Queue;

public class JavaPriorityQueueExamples {

    public static void main(String[] args) {
        Queue intQueue = new PriorityQueue();
        // Inserts the specified element into this priority queue.
        intQueue.offer(10);
        intQueue.offer(1);
        intQueue.offer(5);
        intQueue.offer(9);
        
        // E poll(): Retrieves and removes the head of this queue
        System.out.println(intQueue.remove());
        /*
         * 1
         */
        
        // Retrieves, but does not remove, the head of this queue
        int head = intQueue.peek();
        System.out.println("headValue = " + head); // headValue = 5
        
        // Inserts the specified element into this priority queue.
        intQueue.add(7);
        intQueue.add(2);
        
        head = intQueue.element();
        System.out.println("headValue = " + head); // headValue = 2
        
        // Removes a single instance of the specified element from this queue, if it is present.
        boolean containOrNot = intQueue.remove(9);
        System.out.println(containOrNot); // true
        
        System.out.println("---");
        
        while(!intQueue.isEmpty()) {
            System.out.println(intQueue.poll());
        }
        
        /*
         * 2
         * 5
         * 7
         * 10
         */
    }
}
  • In above example, we use PriorityQueue() Constructor to create a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

  • add() and offer() method, both can insert an element to a PriorityQueue, But what is the difference?

  • The offer method inserts an element if possible, otherwise returning false.

  • This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception.

  • The remove() and poll() methods remove and return the head of the queue.
    -> BUT when the queue is empty, the remove() method throws an exception, while the poll() method returns null.

  • The element() and peek() retrive the head's value of the queue and NOT remove. When the queue is empty:

  • element() throws NoSuchElementException.

  • peek() returns null.

Now we do an example to iterate all elements of a Java PriorityQueue:

  • using iterator(): to return an iterator over the elements in the queue.
  • using toArray(): to return an array containing all the elements in the queue.

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class JavaPriorityQueueExamples{

    public static void main(String[] args) {
        Queue<Integer> intQueue = new PriorityQueue<Integer>();
        // Inserts the specified element into this priority queue.
        intQueue.offer(10);
        intQueue.offer(1);
        intQueue.offer(5);
        intQueue.offer(9);
        
        // Returns an iterator over the elements in this queue.
        Iterator<Integer> intIterator = intQueue.iterator();
        
        while (intIterator.hasNext()) 
            System.out.print(intIterator.next() + " ");
        /*
         * 1 9 5 10 
         */
        
        System.out.println();
        
        // Returns an array containing all of the elements in this queue.
        Object[] intArr =  intQueue.toArray();
        for(int i=0; i<intArr.length; i++) {
            System.out.print(intArr[i] + " ");
        }
        /*
         * 1 9 5 10 
         */
    }
}

Java PriorityQueue with String Example

  • Example: Create Java String PriorityQueue using Natural Ordering of String

import java.util.PriorityQueue;
import java.util.Queue;

public class JavaPriorityQueueExamples {

    public static void main(String[] args) {
        Queue strQueue = new PriorityQueue();
        
        // Inserts the specified element into this priority queue.
        strQueue.offer("Jack");
        strQueue.offer("Charlie");
        strQueue.offer("Joe");
        strQueue.offer("George");
        
        while(!strQueue.isEmpty()) {
            System.out.print(strQueue.poll() + " ");
        }
        
        /*
         * -> Charlie George Jack Joe   
         */
    }
}

Create Java PriorityQueue with a custom Comparator

  • Create a Java PriorityQueue using a Custom Comparator that compares two Strings by their length:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class JavaPriorityQueueExamples {

    public static void main(String[] args) {
        Queue strQueue = new PriorityQueue((Comparator super String>) new Comparator() {
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        
        // Inserts the specified element into this priority queue.
        strQueue.offer("Jack");
        strQueue.offer("Charlie");
        strQueue.offer("Joe");
        strQueue.offer("George");
        
        while(!strQueue.isEmpty()) {
            System.out.print(strQueue.poll() + " ");
        }
    }
}

-> Output:


Joe Jack George Charlie

Java PriorityQueue with Custom Object Example

  • Create an Java Developer class:

class Developer{
    Integer id;
    String name;
    Double salary;
    
    public Developer(Integer id, String name, Double salary){
        this.id = id;
        this.name = name;
        this.salary = salary;
    }
    
    public int getId() {
        return this.id;
    }
    
    public String getName() {
        return this.name;
    }
    
    public Double getSalary() {
        return this.salary;
    }
    
    public String toString() {
        return String.format("[id = %d, name = %s, salary = %.2f]", id, name, salary);
    }
}
  • Implement Comparable interface to compare its elements and order them accordingly as below:

class Developer implements Comparable{
    ...
    
    @Override
    public int compareTo(Developer d) {
        if(this.getSalary() > d.getSalary()) {
            return 1;
        } else if (this.getSalary() < d.getSalary()) {
            return -1;
        } else {
            return 0;
        }
    }
}
  • Create a Java PriorityQueue Example with Developer class:

import java.util.PriorityQueue;
import java.util.Queue;

public class JavaPriorityQueueExamples {

    public static void main(String[] args) {
        Queue devQueue = new PriorityQueue();
        
        // Inserts the specified element into this priority queue.
        devQueue.offer(new Developer(1, "Jack", 6000.0));
        devQueue.offer(new Developer(4, "Joe", 7000.0));
        devQueue.offer(new Developer(10, "Davis", 6500.0));
        devQueue.offer(new Developer(6, "Mary", 5700.0));
        
        while(!devQueue.isEmpty()) {
            System.out.println(devQueue.poll());
        }       
    }
}

-> Output:


/*
 * [id = 6, name = Mary, salary = 5700,00]
 * [id = 1, name = Jack, salary = 6000,00]
 * [id = 10, name = Davis, salary = 6500,00]
 * [id = 4, name = Joe, salary = 7000,00]
 */

-> The Developer with smallest salary is removed first

Conclusion

We had learned how to work with Java PriorityQueue by examples:

  • Create Java PriorityQueue with Natural Ordering of Elements.
  • Create Java PriorityQueue with Custom Comparator.
  • Create Java PriorityQueue with Custom Object that implements Comparable interface.
  • Do a list operations of Java PriorityQueue: offer, peek, poll, remove...

Happy Learning! See you later!

Top comments (0)