Monday 16 January 2017

PiorityQueue in Java

PiorityQueue(=belongs to the Java Collections Framework) is an unbounded Queue, which is based on  priority heap and it is an implementation of Queue interface. It can be used to keep elements in a particular order, according to their natural order (=Comparable) or custom order defined by Comparator interface based on each element’s priority.

PriorityQueue is not synchronized i.e. it cannot be safely shared between multiple threads. To avoid the Concurrent Modification Exception, PriorityBlockingQueue(= thread-safe) can be used in multithreaded environment.

Priority queue provides O(log(n)) time performance for common enqueing and dequeing methods e.g. offer(), poll() and add(), but constant time for retrieval methods e.g. peek() and element().

It was introduced in JDK 1.5.

Java PriorityQueue key points:
1. A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.

public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator)
If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.

2. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

3. null is not allowed in this Collection. It will throw the NullPointerException.

4. The head of this queue is the least element with respect to the specified ordering.

5. Ordering ties between the PriorityQueue elements are decided arbitrarily (=on the basis of random choice).

5. PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.

6. PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.

7. The iterator() of this PriorityQueue does not guarantee for traversal of the Queue elements in any particular order.

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

public class PriorityQueueTest {

      public static void main(String args[]) {

            Queue<MobilePhone> items = new PriorityQueue<MobilePhone>();
            items.add(new MobilePhone("Samsung", 100));
            items.add(new MobilePhone("Iphone", 400));
            items.add(new MobilePhone("Blackberry", 200));
            items.add(new MobilePhone("HTC", 300));

            System.out.println("Mobiles phones list: ");
            System.out.println(items);
      }
}

class MobilePhone implements Comparable<MobilePhone> {
     
      private String name;
      private int price;

      public MobilePhone(String name, int price) {
            this.name = name;
            this.price = price;
      }

      public String getName() {
            return name;
      }

      @Override
      public int compareTo(MobilePhone phone) {
            return this.price - phone.price;
      }

      @Override
      public String toString() {
            return String.format("Brand:%s Price: $%d", name, price);
      }     
}

References:

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...