当前位置:首页 > 开发 > 互联网 > 正文

Java Priority Queue (PriorityQueue) Example

发表于: 2013-08-09   作者:cywhoyi   来源:转载   浏览次数:
摘要: We know that Queue follows First-In-First-Out model but sometimes we need to process the objects in the queue based on the priority. For example, let’s say we have an application that g

We know that Queue follows First-In-First-Out model but sometimes we need to process the objects in the queue based on the priority. For example, let’s say we have an application that generates stocks reports for daily trading session and it processes a lot of data and takes time to process it. So customers are sending request to the application that is actually getting queued but we want to process premium customers first and standard customers after them. So in this casePriorityQueue implementation in java can be really helpful.

PriorityQueue class was introduced in Java 1.5 and part of Java Collections Framework. PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order or we can provide a Comparator for ordering at the time of instantiation of queue.

PriorityQueue doesn’t allow null values and we can’t create PriorityQueue of Objects that are non-comparable, for example any custom classes we have. We use java Comparable and Comparator interfaces for sorting Objects and PriorityQueue use them for priority processing of it’s elements.

The head of the priority queue is the least element based on the natural ordering or comparator based ordering, if there are multiple objects with same ordering, then it can poll any one of them randomly. When we poll the queue, it returns the head object from the queue.

PriorityQueue size is unbounded but we can specify the initial capacity at the time of it’s creation. When we add elements to the priority queue, it’s capacity grows automatically.

PriorityQueue is not thread safe, so java provides PriorityBlockingQueue class that implements the BlockingQueue interface to use in java multi-threading environment.

PriorityQueue implementation provides O(log(n)) time for enqueing and dequeing method. Let’s see an example of PriorityQueue for natural ordering as well as with Comparator.

We have our custom class Customer that doesn’t provide any type of ordering, so when we will try to use it with PriorityQueue we should provide a comparator object for that.

package org.dxy.util;

public class Customer {

	private int id;
	private String name;

	public Customer(int i, String n) {
		this.id = i;
		this.name = n;
	}

	public int getId() {
		return id;
	}

	public String getName() {
		return name;
	}

}

 We will use java random number generation to generate random customer objects. For natural ordering, I will use Integer that is also ajava wrapper class.

Here is our final test code that shows how to use PriorityQueue.

package org.dxy.util;

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

/**
 * 
 * @author chenyang
 * 
 */
public class PriorityQueueExample {

	public static void main(String[] args) {

		// natural ordering example of priority queue
		Queue<Integer> integerPriorityQueue = new PriorityQueue<Integer>(7);
		Random rand = new Random();
		for (int i = 0; i < 7; i++) {
			integerPriorityQueue.add(new Integer(rand.nextInt(100)));
		}
		for (int i = 0; i < 7; i++) {
			Integer in = integerPriorityQueue.poll();
			System.out.println("Processing Integer:" + in);
		}

		// PriorityQueue example with Comparator
		Queue<Customer> customerPriorityQueue = new PriorityQueue<Customer>(7,
				idComparator);
		addDataToQueue(customerPriorityQueue);

		pollDataFromQueue(customerPriorityQueue);

	}

	// Comparator anonymous class implementation
	public static Comparator<Customer> idComparator = new Comparator<Customer>() {

		@Override
		public int compare(Customer c1, Customer c2) {
			return (int) (c1.getId() - c2.getId());
		}
	};

	// utility method to add random data to Queue
	private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
		Random rand = new Random();
		for (int i = 0; i < 7; i++) {
			int id = rand.nextInt(100);
			customerPriorityQueue.add(new Customer(id, "Pankaj " + id));
		}
	}

	// utility method to poll data from queue
	private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
		while (true) {
			Customer cust = customerPriorityQueue.poll();
			if (cust == null)
				break;
			System.out.println("Processing Customer with ID=" + cust.getId());
		}
	}

}

 From output it’s clear that least element was at head and got polled first. If we won’t provide comparator while creatingcustomerPriorityQueue, it will throw ClassCastException at runtime.

1 Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
2     at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
3     at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
4     at java.util.PriorityQueue.offer(PriorityQueue.java:329)
5     at java.util.PriorityQueue.add(PriorityQueue.java:306)
6     at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
7     at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)

 

Java Priority Queue (PriorityQueue) Example

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一、二叉堆含义及属性: 堆(heap)亦被称为:优先队列(priority queue),是计算机科学中一类特殊的
比较好的java书上都写着不要试图用java线程的优先级来确定线程的执行顺序,不过知道下java线程优先
Some important applications of priority queues include simulation systems, where the keys cor
· 学后心得体会与部分习题实现 心得体会: 曾经只是了解了优先队列的基本性质,并会调用C++ STL库中
PriorityQueue介绍 在平时的编程工作中似乎很少碰到PriorityQueue(优先队列) ,故很多人一开始看
开发中有时会遇到这样的情况。要求某个调度器去调度一些任务,这些任务放在队列里。任务本身有优先
http://blog.csdn.net/yangzhongblog/article/details/8607632 1 概念 优先级队列PriorityQueue是不
2.4.5 堆排序 我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的有限队列
这一次,笔者使用了STL库中的优先级队列(Priority Queue)来完成Dijkstra算法中extract-min()语句(
一、容器适配器 stack queue priority_queue stack、queue、priority_queue 都不支持任一种迭代器,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号