文档章节

Java PriorityQueue class

Ciet
 Ciet
发布于 01/17 22:43
字数 933
阅读 96
收藏 0

Java PriorityQueue class is a queue data structure implementation in which objects are processed based on their priority. It is different from standard queues where FIFO (First-In-First-Out) algorithm is followed.

In a priority queue, added objects are according to their priority. By default, the priority is determined by objects’ natural ordering. Default priority can be overridden by a Comparator provided at queue construction time.

Priority Queue

Priority Queue

1. PriorityQueue Features

Let’s note down few important points on the PriorityQueue.

  • PriorityQueue is an unbounded queue and grows dynamically. The default initial capacity is '11' which can be overridden using initialCapacity parameter in appropriate constructor.
  • It does not allow NULL objects.
  • Objects added to PriorityQueue MUST be comparable.
  • The objects of the priority queue are ordered by default in natural order.
  • A Comparator can be used for custom ordering of objects in the queue.
  • The head of the priority queue is the least element based on the natural ordering or comparator based ordering. When we poll the queue, it returns the head object from the queue.
  • If multiple objects are present of same priority the it can poll any one of them randomly.
  • PriorityQueue is not thread safe. Use PriorityBlockingQueue in concurrent environment.
  • It provides O(log(n)) time for add and poll methods.

2. Java PriorityQueue Example

Let’s see how object’s ordering impacts the add and remove operations in PriorityQueue. In given examples, the objects are of type Employee. Employee class implements Comparable interface which makes objects comparable by employee 'id' field, by default.

Employee.java |

public class Employee implements Comparable<employee> {

private Long id;

private String name;

private LocalDate dob;

public Employee(Long id, String name, LocalDate dob) {

super();

this.id = id;

this.name = name;

this.dob = dob;

}

@Override

public int compareTo(Employee emp) {

return this.getId().compareTo(emp.getId());

}

//Getters and setters

@Override

public String toString() {

return "Employee [id=" + id + ", name=" + name + ", dob=" + dob + "]";

}

}

|

2.1. Natural Ordering

Java PriorityQueue example to add and poll elements which are compared based on their natural ordering.

PriorityQueue Example |

PriorityQueue<employee> priorityQueue = new PriorityQueue<>();

priorityQueue.add(new Employee(1l, "AAA", LocalDate.now()));

priorityQueue.add(new Employee(4l, "CCC", LocalDate.now()));

priorityQueue.add(new Employee(5l, "BBB", LocalDate.now()));

priorityQueue.add(new Employee(2l, "FFF", LocalDate.now()));

priorityQueue.add(new Employee(3l, "DDD", LocalDate.now()));

priorityQueue.add(new Employee(6l, "EEE", LocalDate.now()));

while(true)

{

Employee e = priorityQueue.poll();

System.out.println(e);

if(e == null) break;

}

|

Program Output.

Console |

Employee [id=1, name=AAA, dob=2018-10-31]

Employee [id=2, name=FFF, dob=2018-10-31]

Employee [id=5, name=BBB, dob=2018-10-31]

Employee [id=4, name=CCC, dob=2018-10-31]

Employee [id=3, name=DDD, dob=2018-10-31]

Employee [id=6, name=EEE, dob=2018-10-31]

|

2.2. Custom Ordering using Comparator

Let’s redefine the custom ordering using Java 8 lambda based comparator syntax and verify the result.

PriorityQueue Example |

//Comparator for name field

Comparator<employee> nameSorter = Comparator.comparing(Employee::getName);

PriorityQueue<employee> priorityQueue = new PriorityQueue<>( nameSorter );

priorityQueue.add(new Employee(1l, AAA, LocalDate.now()));

priorityQueue.add(new Employee(4l, CCC, LocalDate.now()));

priorityQueue.add(new Employee(5l, BBB, LocalDate.now()));

priorityQueue.add(new Employee(2l, FFF, LocalDate.now()));

priorityQueue.add(new Employee(3l, DDD, LocalDate.now()));

priorityQueue.add(new Employee(6l, EEE, LocalDate.now()));

while(true)

{

Employee e = priorityQueue.poll();

System.out.println(e);

if(e == null) break;

}

|

Program Output.

Console |

Employee [id=1, name=AAA, dob=2018-10-31]

Employee [id=5, name=BBB, dob=2018-10-31]

Employee [id=4, name=CCC, dob=2018-10-31]

Employee [id=3, name=DDD, dob=2018-10-31]

Employee [id=6, name=EEE, dob=2018-10-31]

Employee [id=2, name=FFF, dob=2018-10-31]

|

3. Java PriorityQueue Constructors

PriorityQueue class provides 6 different ways to construct a priority queue in Java.

  • PriorityQueue() : constructs empty queue with the default initial capacity (11) that orders its elements according to their natural ordering.
  • PriorityQueue(Collection c) : constructs empty queue containing the elements in the specified collection.
  • PriorityQueue(int initialCapacity) : constructs empty queue with the specified initial capacity that orders its elements according to their natural ordering.
  • PriorityQueue(int initialCapacity, Comparator comparator) : constructs empty queue with the specified initial capacity that orders its elements according to the specified comparator.
  • PriorityQueue(PriorityQueue c) : constructs empty queue containing the elements in the specified priority queue.
  • PriorityQueue(SortedSet c) : constructs empty queue containing the elements in the specified sorted set.

4. Java PriorityQueue Methods

PriorityQueue class has below given important methods, you should know.

  • boolean add(object) : Inserts the specified element into this priority queue.
  • boolean offer(object) : Inserts the specified element into this priority queue.
  • boolean remove(object) : Removes a single instance of the specified element from this queue, if it is present.
  • Object poll() : Retrieves and removes the head of this queue, or returns null if this queue is empty.
  • Object element() : Retrieves, but does not remove, the head of this queue, or throws NoSuchElementException if this queue is empty.
  • Object peek() : Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
  • void clear() : Removes all of the elements from this priority queue.
  • Comparator comparator() : Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.
  • boolean contains(Object o) : Returns true if this queue contains the specified element.
  • Iterator iterator() : Returns an iterator over the elements in this queue.
  • int size() : Returns the number of elements in this queue.
  • Object[] toArray() : Returns an array containing all of the elements in this queue.

本文转载自:https://howtodoinjava.com/java/collections/java-priorityqueue/

Ciet
粉丝 0
博文 68
码字总数 70
作品 0
南京
其他
私信 提问
加载中

评论(0)

Java PriorityQueue && PriorityBlockingQueue

Java PriorityQueue && PriorityBlockingQueue 我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时...

秋风醉了
2015/01/12
226
0
聊聊Elasticsearch的TaskScheduler

序 本文主要研究一下Elasticsearch的TaskScheduler TaskScheduler elasticsearch-7.0.1/libs/nio/src/main/java/org/elasticsearch/nio/TaskScheduler.java TaskScheduler定义了DelayedTask......

go4it
2019/05/30
24
0
[转] Java 无界阻塞队列 DelayQueue 入门实战

原文出处:http://cmsblogs.com/ 『chenssy』 DelayQueue是一个支持延时获取元素的无界阻塞队列。里面的元素全部都是“可延期”的元素,列头的元素是最先“到期”的元素,如果队列里面没有元...

泥瓦匠BYSocket
2019/10/17
38
0
Java反序列化漏洞的原理分析

  *本文原创作者:Moonlightos,本文属FreeBuf原创奖励计划,未经许可禁止转载   世界上有三件事最难:      把别人的钱装进自己的口袋里   把自己的想法装进别人的脑袋里   让自...

FreeBuf
2018/05/04
0
0
Android ThreadLocal+PriorityQueue构建多线程队列

一、消息队列 Android中使用了很多消息队列,如Intent,Handler,BroadcastReceiver等。使用消息队列的目的是防止线程阻塞并且将不能及时执行的任务缓存起来,从而提高系统的运行效率。 为了使...

IamOkay
2014/11/03
1.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

Minecraft Fabric Client 教程 #5 添加Event、Sprint和ToggleCommand

首发于Enaium的个人博客 添加Event 下载 放在cn.enaium.excel里 然后在Excel.java里面添加EventManager public enum Excel { [...] public EventManager eventManager; pu......

Enaium
9分钟前
25
0
记 S3Service 代码中的一个低级错误

osgl-storage 是 osgl 工具箱 中用于简化存储的. 其特点是接口简单, 支持多种存储引擎插件, 包括本地文件系统, AWS S3, Azure Blob, 七牛 Kodo 服务. 最近老码农在一次调试中偶然发现了 osgl...

开源老码农
11分钟前
187
0
如何实现Samba文件共享服务

目标:实现Samba文件共享服务 试验环境:两台主机服务端:192.168.56.11客户端:192.168.56.12 配置用户认证共享 服务端操作: 1.关闭防火墙,关闭selunix [root@hejie ~]# setenforce 0[...

linuxprobe2020
13分钟前
18
0
SQL Server Profiler - 如何过滤跟踪以仅显示来自一个数据库的事件?

如何将SQL Server Profiler跟踪限制为特定数据库? 我看不到如何过滤跟踪,看不到我连接的实例上的所有数据库的事件。 #1楼 在Trace properties> Events Selection选项卡下>选择show all co...

技术盛宴
13分钟前
25
0
Kafka配置及常用命令笔记

一、kafka配置 1. 服务端 server.properties #broker 的全局唯一编号,不能重复broker.id=0#删除 topic 功能使能delete.topic.enable=true#处理网络请求的线程数量num.network.thr...

liddblog
17分钟前
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部