HelloKoding

Practical coding guides

PriorityQueue in Java

There’re two priority queue implementations in Java, PriorityQueue and PriorityBlockingQueue. They are both based on binary heap data structure

Map implementations in Java Collections Framework

The PriorityQueue class

  • Designed for holding elements prior to processing in a single-threaded environment. All operations are not thread-safe
  • Supported since Java 1.5

PriorityQueue features

  • Elements are ordered according to their Comparable natural ordering or by a Comparator provided at queue construction time
  • No guarantees about the ordering of elements with equal priority. If you need it, consider defining custom classes or comparators that use a secondary key to break ties in primary priority values
  • The iterator() method is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray())
  • Does not permit null elements. Comparable PriorityQueue also does not permit insertion of non-comparable objects
  • Capacity is unbounded and auto grown internally

PriorityQueue operations

  • add(e) or offer(e), adds element into the queue
  • remove() or poll(), removes and retrieves the highest priority element
  • element() or peek(), retrieves the highest priority element

PriorityQueue usage examples

PriorityQueueTest.java

package com.hellokoding.java.collections;

import org.junit.Assert;
import org.junit.Test;

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

public class PriorityQueueTest {
    @Test(expected = ClassCastException.class)
    public void whenAddNonComparable_thenThrowException(){
        PriorityQueue<BookNonComparable> books = new PriorityQueue<>();
        books.add(new BookNonComparable("C"));
        books.add(new BookNonComparable("A"));
        books.add(new BookNonComparable("D"));
    }

    @Test
    public void whenAddComparable_thenSuccess(){
        PriorityQueue<BookComparable> books = new PriorityQueue<>();
        books.add(new BookComparable("C"));
        books.add(new BookComparable("A"));
        books.add(new BookComparable("D"));

        Assert.assertEquals("A", books.peek().title);
        Assert.assertEquals("A", books.remove().title);
        Assert.assertEquals("C", books.peek().title);
    }

    @Test
    public void whenAddComparator_thenSuccess(){
        Comparator<BookNonComparable> comparator = Comparator.comparing(BookNonComparable::getTitle);
        PriorityQueue<BookNonComparable> books = new PriorityQueue<>(comparator);
        books.offer(new BookNonComparable("C"));
        books.offer(new BookNonComparable("A"));
        books.offer(new BookNonComparable("D"));

        Assert.assertEquals("A", books.peek().title);
        Assert.assertEquals("A", books.poll().title);
        Assert.assertEquals("C", books.peek().title);
    }

    @Test(expected = NullPointerException.class)
    public void whenAddNull_thenThrowException(){
        PriorityQueue<BookNonComparable> books = new PriorityQueue<>();
        books.add(null);
    }

    static class BookComparable implements Comparable<BookComparable> {
        String title;

        BookComparable(String title) {
            this.title = title;
        }

        @Override
        public int compareTo(BookComparable o) {
            return this.title.compareTo(o.title);
        }
    }

    static class BookNonComparable {
        String title;

        BookNonComparable(String title) {
            this.title = title;
        }

        public String getTitle(){
            return this.title;
        }

        @Override
        public String toString() {
            return this.title;
        }
    }
}

The PriorityBlockingQueue class

  • Designed to be used primarily for producer-consumer queues in a multi-threaded environment. All public operations are protected with a single lock
  • PriorityBlockingQueue uses the same ordering rules as PriorityQueue and supplies blocking retrieval operations
  • Supported since Java 1.5

PriorityBlockingQueue usage examples

PriorityBlockingQueueExample.java

package com.hellokoding.java.collections;

import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class PriorityBlockingQueueExample {
    private static AtomicInteger seq = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        PriorityBlockingQueue<BookComparable> q = new PriorityBlockingQueue<>(10);

        Thread t1 = new Thread(new Producer(q));
        Thread t2 = new Thread(new Consumer(q));
        Thread t3 = new Thread(new Consumer(q));

        t1.start();
        t2.start();
        t3.start();

        t1.join();
        t2.join();
        t3.join();
    }

    static class Producer implements Runnable {
        private final PriorityBlockingQueue<BookComparable> queue;

        Producer(PriorityBlockingQueue<BookComparable> q) { queue = q; }

        public void run() {
            try {
                for (int i = 0; i < 10; i++) {
                    queue.put(produce());
                    Thread.sleep(10);
                }
            } catch(InterruptedException ex){
                System.out.println(ex);
            }
        }

        BookComparable produce() {
            BookComparable bookComparable = new BookComparable();
            System.out.printf("Put %s %s", bookComparable, System.lineSeparator());

            return bookComparable;
        }
    }

    static class Consumer implements Runnable {
        private final PriorityBlockingQueue<BookComparable> queue;

        Consumer(PriorityBlockingQueue<BookComparable> q) { queue = q; }

        public void run() {
            try {
                while (true) {
                    consume(queue.take());
                    Thread.sleep(10);
                }
            } catch (InterruptedException ex) {
                System.out.println(ex);
            }
        }

        void consume(BookComparable bookComparable) {
            System.out.printf("Take %s %s", bookComparable, System.lineSeparator());
        }
    }

    static class BookComparable implements Comparable<BookComparable> {
        Integer id ;

        BookComparable() {
            this.id = seq.incrementAndGet();
        }

        @Override
        public int compareTo(BookComparable o) {
            return o.id.compareTo(this.id);
        }

        @Override
        public String toString() {
            return this.id.toString();
        }
    }
}
Follow HelloKoding