Java优先队列-IGI

时间：2020-02-23 14:37:23 　来源:igfitidea点击:

我们不时需要按特定顺序处理队列中的项目。
优先级队列是完成任务的数据结构。
Java优先级队列与"普通"队列不同。
代替"先进先出"，它按优先级顺序检索项目。

Java优先队列

通过内部使用优先级堆实现，java.util.PriorityQueue类为我们提供了这种数据类型的实现。
Java PriorityQueue是一个无界队列。
它是在Java 1.5中引入的，并在Java SE 8版本中得到了增强。
PriorityQueue通过遵循"优先级堆"数据结构在内部实现。

Java PriorityQueue构造函数

PriorityQueue()–使用默认初始容量(即11)创建一个PriorityQueue
PriorityQueue(Collection c)–使用指定集合中的元素创建一个PriorityQueue
PriorityQueue(int initialCapacity)–创建具有指定初始容量的PriorityQueue
PriorityQueue(int initialCapacity，Comparator比较器)–创建具有提供的初始容量的PriorityQueue，其元素的顺序根据指定的比较器
PriorityQueue(PriorityQueue c)–创建一个包含指定优先级队列中元素的PriorityQueue
PriorityQueue(SortedSet c)–创建一个包含指定排序集中的元素的PriorityQueue

除非我们在创建它时提供" Comparator"，否则Priority Queue元素将按其自然顺序进行排序。
默认情况下，元素按升序排列，因此队列的开头是优先级最低的元素。

如果有两个元素可以同时成为负责人，则这种联系会被任意打破。

Java PriorityQueue示例

让我们创建一个包含各种任务的" PriorityQueue"：

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

这将创建一个PriorityQueue任务，这些任务将按照" String"的自然顺序进行排序。
让我们创建另一个PriorityQueue，以自然顺序的相反顺序对任务进行排序。
因此，我们需要通过一个比较器：

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue方法

现在，让我们看一下PriorityQueue可用的所有方法并使用它们：

布尔值add(E e)–此方法将指定的元素插入队列。

我们已经使用这种方法在队列中添加了5个任务。

比较器比较器()–此方法返回用于对队列中的元素进行排序的比较器。
如果未指定比较器，并且队列根据其元素的自然顺序排序，则返回null。

因此，如果我们这样做：
输出将是：

boolean contains(Object o)–如果队列包含指定的元素，则返回true。

让我们检查" task3"是否属于优先级队列任务：
打印：

boolean offer(E e)–就像add()方法一样，此方法也将元素添加到队列中。

对于容量受限的队列，offer()和add()方法实际上有些不同，但是对于PriorityQueue，两者是相同的。
与add()不同，offer()不会引发异常，即使它未能将元素添加到队列中也是如此。

E peek()–检索此队列的开头，如果此队列为空，则返回null。
换句话说，它返回具有最高优先级的元素。

所以下面的代码：
给我们：

E poll()–此方法还检索队列的头(优先级最高的元素)，如果队列为空，则返回null。
但是与peek()不同，它还删除了元素。

因此，如果我们调用poll()：
然后偷看：
我们将提供以下输出：

int size()–返回队列中元素的数量。
boolean remove(Object o)-从队列中删除指定的元素(如果存在)。
如果存在两个相同的元素，则仅删除其中之一。
Object [] toArray()–返回包含队列中所有元素的数组。
T [] toArray(T [] a)–返回包含队列中所有元素的数组，并且返回的数组的类型为指定数组的类型。
Iterator iterator()–返回队列的迭代器。
void clear()–从队列中删除所有元素。

除此之外，PriorityQueue还继承了Collection和Object类的方法。

Java PriorityQueue时间复杂度

对于入队和出队方法，时间复杂度为O(log(n))
对于remove(Object)和contains(Object)方法，时间复杂度是线性的
对于检索方法，它具有恒定的时间复杂度

优先级队列的此实现不是线程安全的。
因此，如果需要同步访问，则需要使用PriorityBlockingQueue。

Java优先队列