Java 中的优先级队列详细介绍-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java 中的优先级队列详细介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.介绍

当应该根据优先级处理对象时，将使用 PriorityQueu。
众所周知Queue是遵循先进先出算法的，但是有时候需要按照优先级来处理队列中的元素，这时候PriorityQueue就派上用场了。
PriorityQueue 基于优先级堆。
优先级队列的元素根据自然顺序排序，或者由队列构造时提供的比较器排序，具体取决于使用的构造函数

在下面的优先级队列中，具有最大 ASCII 值的元素将具有最高优先级。

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

where E is the type of elements held in this queue

Priority Queue的几个要点如下：

PriorityQueue 不允许 null。
我们不能创建不可比较对象的 PriorityQueue PriorityQueue 是非绑定队列。
该队列的头部是相对于指定顺序的最少元素。
如果多个元素绑定到最小值，则头部就是这些元素之一——绑定被任意打破。
由于 PriorityQueue 不是线程安全的，java 提供了实现 BlockingQueue 接口的 PriorityBlockingQueue 类以在 java 多线程环境中使用。
队列检索操作 poll、remove、peek 和 element 访问队列头部的元素。
它为添加和轮询方法提供 O(log(n)) 时间。它继承了 AbstractQueue、AbstractCollection、Collection 和 Object 类的方法。

构造函数：

PriorityQueue()：创建一个具有默认初始容量 (11) 的 PriorityQueue，它根据元素的自然顺序对其元素进行排序
PriorityQueue<E> pq = new PriorityQueue<E>();
PriorityQueue(Collection c)：创建一个包含指定集合中的元素的 PriorityQueue。
PriorityQueue<E> pq = new PriorityQueue<E>(Collection<E> c);
PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的 PriorityQueue，它根据元素的自然顺序对其元素进行排序。
PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);
PriorityQueue(int initialCapacity, Comparator comparator)：创建一个具有指定初始容量的 PriorityQueue，它根据指定的比较器对其元素进行排序。
PriorityQueue<E> pq = new PriorityQueue(int initialCapacity, Comparator<E> comparator);
PriorityQueue(PriorityQueue c)：创建一个包含指定优先级队列中元素的PriorityQueue。PriorityQueue<E> pq = new PriorityQueue(PriorityQueue<E> c);
PriorityQueue(SortedSet c)：创建一个包含指定排序集合中元素的PriorityQueue
PriorityQueue<E> pq = new PriorityQueue<E>(SortedSet<E> c);

下面的例子解释了优先级队列的以下基本操作。

boolean add(E element)：此方法将指定元素插入此优先级队列。
public peek()：此方法检索但不删除此队列的头部，如果此队列为空，则返回 null。
public poll()：此方法检索并移除此队列的头部，如果此队列为空，则返回 null。

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
        pQueue.add(10);
        pQueue.add(20);
        pQueue.add(15);
        System.out.println(pQueue);
        System.out.println(pQueue.peek());//检索但不删除此队列的头部
        System.out.println(pQueue.poll());//检索并移除此队列的头部
        System.out.println(pQueue.peek());
    }
}

[10, 20, 15]
10
10
15

2.对 PriorityQueue 的操作

让我们看看如何在优先级队列类上执行一些常用的操作。

1. 添加元素

添加元素：为了在优先级队列中添加元素，我们可以使用 add() 方法。
插入顺序不保留在 PriorityQueue 中。元素按优先级顺序存储，默认为升序。

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < 3; i++) {
            pq.add(i);
            pq.add(1);

        }
        System.out.println(pq);
    }
}

[0, 1, 1, 1, 2, 1]

我们不会通过打印 PriorityQueue 来获得已排序的元素。

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println(pq);
    }
}

[For, Geeks, Geeks]

2. 删除元素

删除元素：为了从优先队列中删除一个元素，我们可以使用remove()方法。
如果有多个这样的对象，则删除第一个出现的对象。除此之外，poll() 方法还用于移除头部并将其返回。

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println("Initial PriorityQueue " +pq);
        pq.remove("Geeks");//移除指定元素

        System.out.println("After Remove - " + pq);

        System.out.println("Poll Method - " + pq.poll());//从头部移除

        System.out.println("Final PriorityQueue - " + pq);
    }
}

Initial PriorityQueue [For, Geeks, Geeks]
After Remove - [For, Geeks]
Poll Method - For
Final PriorityQueue - [Geeks]

3. 访问元素

访问元素：由于Queue遵循先进先出的原则，我们只能访问队列的头部。
要访问优先级队列中的元素，我们可以使用 peek() 方法。

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println("Initial PriorityQueue " +pq);
        String element = pq.peek();
        System.out.println("Accessed Element: " + element);
    }
}

Initial PriorityQueue [For, Geeks, Geeks]
Accessed Element: For

4.迭代PriorityQueue

迭代PriorityQueue：有多种方法可以迭代PriorityQueue。
最著名的方法是将队列转换为数组并使用 for 循环遍历。但是，队列还有一个内置的迭代器，可用于遍历队列。文章来源地址https://www.toymoban.com/news/detail-627665.html

public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println(pq);
        Iterator it= pq.iterator();
        while (it.hasNext()){
            System.out.println(it.next()+" ");
        }
    }
}

[For, Geeks, Geeks]
For 
Geeks 
Geeks

3.PriorityQueue 类中的方法

方法	描述
add(E e)	将指定元素插入此优先级队列。
clear()	从此优先级队列中删除所有元素。
comparator()	返回用于对该队列中的元素进行排序的比较器，如果该队列是根据其元素的自然顺序排序的，则返回 null。
contains(Object o)	如果此队列包含指定元素，则返回 true。
forEach(Consumer<? super E> action)	对 Iterable 的每个元素执行给定的操作，直到处理完所有元素或操作引发异常。
iterator()	返回此队列中元素的迭代器。
offer(E e)	将指定元素插入此优先级队列。
remove(Object o)	从此队列中移除指定元素的单个实例（如果存在）。
removeAll(Collection<?> c)	删除此集合的所有也包含在指定集合中的元素（可选操作）。
removeIf(Predicate<? super E> filter)	移除此集合中满足给定谓词的所有元素。
retainAll(Collection<?> c)	仅保留此集合中包含在指定集合中的元素（可选操作）。
spliterator()	在此队列中的元素上创建一个后期绑定和快速失败的 Spliterator。
toArray()	返回包含此队列中所有元素的数组。
toArray(T[] a)	返回一个包含此队列中所有元素的数组；返回数组的运行时类型是指定数组的类型。