PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)
优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节
简单应用:
package test; import java.util.PriorityQueue; public class PriorityQueueTest1 { @SuppressWarnings("unchecked") public static void main(String[] args) { PriorityQueue queue = new PriorityQueue(); queue.add("AAAAA"); // Add接受的参数是Obj,PriorityQueue使用integer String等基本的数据类型时,默认new时有参数,如果不写则是按照默认排序 queue.add("BBBBB"); queue.add("CCCCC"); queue.add("DDDDD"); System.out.println(queue.peek()); // 获取但不移除此队列的头 System.out.println(queue.poll()); // 获取并移除此队列的头 System.out.println(queue.poll()); queue.offer("ZZZZZ"); // 将指定的元素插入此优先级队列 System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); // 到这里已经没有元素,打印Null } }
定义比较器:
package test; import java.util.Comparator; import java.util.PriorityQueue; @SuppressWarnings("unchecked") public class PriorityQueueTest2 { private static PriorityQueue queue = new PriorityQueue(10,new Comparators()); public static void main(String[] args) { QueueObject queueObject = new QueueObject(); queueObject.setId(4); queueObject.setObject("AAAAA"); queue.add(queueObject); QueueObject queueObject1 = new QueueObject(); queueObject1.setId(1); queueObject1.setObject("BBBBB"); queue.add(queueObject1); QueueObject queueObject2 = new QueueObject(); queueObject2.setId(3); queueObject2.setObject("CCCCC"); queue.add(queueObject2); System.out.println(((QueueObject)queue.poll()).getObject()); System.out.println(((QueueObject)queue.poll()).getObject()); System.out.println(((QueueObject)queue.poll()).getObject()); } } class QueueObject { private int id; private Object object; public int getId() { return id; } public void setId(int id) { this.id = id; } public Object getObject() { return object; } public void setObject(Object object) { this.object = object; } } @SuppressWarnings("unchecked") class Comparators implements Comparator{ public int compare(Object arg0, Object arg1) { int val1 = ((QueueObject)arg0).getId(); int val2 = ((QueueObject)arg1).getId(); return val1 < val2 ? 0 : 1; } }
注意事项:
注意1:该队列是用数组实现,但是数组大小可以动态增加,容量无限。
注意2:此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。
注意3:不允许使用 null 元素。
注意4:此实现为插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 时间;
为 remove(Object) 和 contains(Object) 方法提供线性时间;
为检索方法(peek、element 和 size)提供固定时间。
注意5:方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。
至于原因可参考下面关于PriorityQueue的内部实现
如果需要按顺序遍历,请考虑使用 Arrays.sort(pq.toArray())。
注意6:可以在构造函数中指定如何排序。如:
PriorityQueue()
使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator comparator)
使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
PriorityQueue的内部实现
PriorityQueue对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。
方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的
请您到ITEYE网站看 java小强 原创,谢谢!
http://cuisuqiang.iteye.com/ !
自建博客地址:http://www.javacui.com/ ,内容与ITEYE同步!
相关推荐
优先级队列头文件priorityqueue.h
优先级队列cpp文件PriorityQueue.cpp
PriorityQueue-MEX-Matlab 优先级队列 matlab
下面的类利用 heapq 模块实现了一个简单的优先级队列: import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority): heapq.heappush(self._...
使用C#中的二进制堆的自定义优先级队列实现。为个人/俱乐部项目编写。 (据我所知)它符合大多数.NET标准。不是线程安全的。 信息 这段代码是从Java项目转换为利用C#功能集并在结构上更合理的东西。虽然原始的Java...
复杂度 时间复杂度 空间复杂度 线性数据结构动态数组(ArrayList) 链表(LinkedList) 单向链表 双向链表 循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) ...优先级队列(PriorityQueue)
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
PriorityQueue:基于二进制堆的最小/最大优先级队列实现 PriorityLookupQueue:基于二进制堆的最小/最大优先级队列实现,具有快速查找 BinarySearchTree:自平衡AVL二进制搜索树 NetCollectionsTests库: ...
这是 C++ STL 优先级队列的 Mexified MATLAB 包装器这个优先队列实现很简单。 然而,它可以用来保存任意对象的“排序”列表。 我们可以只推送它的索引,而不是推送整个对象。 这是通过首先像往常一样将对象存储在 ...
任务的优先队列 基于任务的PriorityQueue的实现在此程序中,用户可以: 注册新任务,并传递名称和优先级 提取并返回列表中优先级最低的任务 清除任务列表 列出所有待处理的任务及其优先级 导入和导出CSV文件中的...
PriorityQueue 优先队列实现C# PriorityQueueLib: 基于二进制堆的最小/最大优先级队列实现PriorityQueueTests: PriorityQueue单元测试
本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考,具体如下: ...class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority):
实现一个优先级队列,每次pop的元素要是优先级高的元素,由于heapq.heapify(list)默认构建一个小顶堆,因此要将priority变为相反数再push,代码如下: import heapq class PriorityQueue(object): 实现一个优先级...
priorityqueue.js Node.js的简单优先级队列数据结构。安装npm install priorityqueuejs例子var PriorityQueue = require ( 'priorityqueuejs' ) ;var queue = new PriorityQueue ( function ( a , b ) { return a . ...
Dart基于二进制堆的优先级队列。 使用add插入元素,并使用removeMax删除最大元素,这在peek观察到。 此实现的独创性在于它提供了一种O(log n) remove方法,该方法使用哈希映射来跟踪堆中元素的位置。 由于维护此...
PriorityQueue PriorityQueue是最小/最大PriorityQueue的Javascript实现。 近期变动 V1.0 在1.0版中,删除了对setComparator(func)和setEquals(func)的支持。 这些方法导致了意外的行为。 需要这些功能时,请...
车道Lane包提供队列,优先级队列,堆栈和双端队列数据结构的实现。 它的设计考虑了简单性,性能和并发使用。优先队列Pqueue是堆优先级队列数据结构的实现。 它可以是最大订购量还是最小订购量,是否已同步以及对于...
使用堆数据结构的性能优先级队列实现。 目录 。尺寸() .toArray() 。清除() 建造 执照 安装 npm install --save @datastructures-js/priority-queue 原料药 此存储库中有两种类型的PriorityQueue:...
Node.js 和浏览器的简单优先级队列数据结构。 安装 作为浏览器的组件: $ component install janogonzalez/priorityqueuejs 作为 Node.js 的 npm: $ npm install priorityqueuejs 如果您只想要一个在 Web 中...
Heap.js JavaScript / TypeScript的高效二进制堆(优先级队列,二进制树)数据结构。 包括JavaScript方法,Python的heapq模块方法和Java的PriorityQueue方法。 易于使用,已知接口,经过测试并有据可查JavaScript二...