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)
|
相关推荐
用linked list来写priority queue
STL 中的 priority_queue priority_queue 是 STL 中的一种容器,可以实现优先级队列的功能。下面,我们将详细介绍 priority_queue 的使用方法和实现原理。 priority_queue 的基本概念 priority_queue 是一种特殊...
Android Priority Job Queue
*push() 将一个元素置于priority queue中 top() 返回priority queue中的“下一个元素” pop() 从priority queue 中移除一个元素 注意:如果priority queue 内没有元素,执行top()和pop()会导致未定义的行为,应该先...
Two-level heaps a new priority queue structure with applications to the single source shortest path problem
本文将深入探讨“前端开源库-js-priority-queue”这一主题,它是一个专门为JavaScript设计的优先级队列实现,为前端开发者提供了一种强大的数据结构,用于优化算法和提高代码执行效率。 **优先级队列简介** 优先级...
在编程语言中,很多库提供了优先队列的实现,例如C++中的`<queue>`库和`<priority_queue>`模板,Java的`java.util.PriorityQueue`类,Python的`heapq`模块等。这些库通常提供上述的基本操作,并且性能高效,因为它们...
算法中优先级队列问题...用堆排序的算法来做的例子
Priority Job Queue is an implementation of a Job Queue specifically written for Android to easily schedule jobs (tasks) that run in the background, improving UX and application stability.
自己编写优类似优先队列数据(priority_queue)的功能,适合上交的课程设计作业
Java通过`PriorityQueue`类实现了优先级队列,该类默认使用自然排序(即对象的`compareTo`方法)或者提供一个比较器(`Comparator`)来指定排序方式。 #### 四、创建优先级队列 在Java中创建优先级队列非常简单: ...
C++中的优先队列(Priority_queue)是一种特殊的数据结构,它遵循“大顶堆”或“小顶堆”的原则,即队列中的元素总是按照优先级进行排序。在这个实例中,我们关注的是如何在C++环境中,特别是使用Visual C++ 2008 ...
从提供的文件内容来看,文档标题为"priority_queue.pdf",描述同样为"priority_queue.pdf",说明该文档是关于优先队列(priority queue)的,它是C++标准模板库(STL)中的一个重要容器。由于文档内容是以OCR扫描...
优先级队列的实现,包括堆的实现,最大堆的生成
@ datastructures-js / priority-queue 使用堆数据结构的性能优先级队列实现。 目录 。尺寸() .toArray() 。清除() 建造 执照 安装 npm install --save @datastructures-js/priority-queue 原料药 此...
var queue = new PriorityQueue(function (a, b) { return a - b; }); // Adding elements to the queue. queue.enqueue(2); queue.enqueue(0); queue.enqueue(1); // Removing the smallest element from the ...
C++ 中”priority_queue” 优先级队列实例详解 1. 简介 标准库队列使用了先进先出(FIFO)的存储和检索策略. 进入队列的对象被放置在尾部, 下一个被取出的元素则取自队列的首部. 标准库提供了两种风格的队列: FIFO ...
Redis优先级队列 redis-priority-queue是一个简单的工作队列,类似于具有以下新增功能: 可以添加具有优先级的项目(介于-9007199254740992和9007199254740992之间) 队列会自动进行重复数据删除(重复的项目在推送...
二、优先队列(Priority Queue) 优先队列是一种数据结构,它能够根据优先级来存储和提取数据。优先队列的实现方式有很多种,常见的有基于数组的实现和基于链表的实现。优先队列的操作有add、remove和peek三个基本...
let mut queue = PriorityQueue :: new (); for priority in 10 .. 10000 { queue. push (priority, String :: from ( format! ( "HelloWorld{}" , priority))); } if let Some (t) = queue. peek ()