一、简介
不允许空值,不支持non-comparable(不可比较)的对象,比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序,并且在排序时会按照优先级处理其中的元素。
优先队列的头是基于自然排序或者Comparator排序的最小元素,当我们获取队列时,返回队列的头对象。
优先队列的大小是不受限制的,但在创建时可以指定初始大小。
PriorityQueue是非线程安全的,所以Java提供了PriorityBlockingQueue(实现BlockingQueue接口用于Java多线程环境。
二、底层实现
此优先队列可以用一个二叉小顶堆表示,故可以使用数组表示。
二叉小顶堆可以用一棵完全二叉树表示,并且任意一个非叶子节点的权值,都不大于其左右子节点的权值。
节点计算:
(1). left = par2 + 1;
(2). right = par2 + 2;
(3). par = (cur - 1) / 2;包含方法
(1). add();//异常
(2). offer();//与add同,异常时返回false
(3). grow();//扩容函数
(4). element();//异常
(5). peek();//与element同,异常时返回null
(6). remove();//取出队头元素,异常
(7). poll();//取出队头元素,null
(8). remove(obj);//多个则删除一个
(9). siftDown();//位置调整方法,调用(8)的时候,会用到