Java中的PriorityQueue

当对象应该基于其优先级进行处理时，使用PriorityQueue。众所周知，队列遵循先进先出算法，但有时需要根据其优先级处理队列的元素，这就是PriorityQueue发挥作用的时候。

PriorityQueue基于优先级堆，其元素根据自然排序或根据在队列构建时提供的比较器排序，具体取决于使用哪个构造函数。

Java中的PriorityQueue

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

Java中的PriorityQueue

声明:

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

其中，E是该队列中包含的元素类型。

该类实现了 Serializable 、 **Iterable ** 、 **Collection ** 和 **Queue ** 接口。

关于PriorityQueue的一些 重要说明 如下:

PriorityQueue不允许null。
我们无法创建对象非可比较的PriorityQueue。
PriorityQueue是未限定队列。
该队列的头是相对于指定排序的最小元素。如果有多个元素具有相同的最小值，则头是其中之一，且绑定是随意的。
由于PriorityQueue不是线程安全的，因此Java提供了实现BlockingQueue接口的PriorityBlockingQueue类来在Java多线程环境中使用。
队列检索操作poll、remove、peek和element访问队列头部的元素。
它提供add和poll方法的O(log(n))时间。
PriorityQueue继承自 AbstractQueue 、 AbstractCollection 、 Collection 和 Object 类。

构造函数:

1. PriorityQueue(): 创建一个PriorityQueue，其默认初始容量为11，并根据其自然排序来排序其元素。

PriorityQueue<E> pq = new PriorityQueue<E>();

**2. PriorityQueue(Collection c): ** 创建一个包含指定集合中的元素的PriorityQueue。

PriorityQueue<E> pq = new PriorityQueue<E>(Collection<E> c);

3. PriorityQueue(int initialCapacity): 创建一个具有指定初始容量的PriorityQueue，并根据其自然排序对其元素进行排序。

PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);

**4. PriorityQueue(int initialCapacity, Comparator comparator): ** 创建一个具有指定初始容量的PriorityQueue，并根据指定的比较器对其元素进行排序。

PriorityQueue<E> = new PriorityQueue(int initialCapacity, Comparator<E> comparator);

**5. PriorityQueue(PriorityQueue c): ** 创建一个包含指定优先队列中的元素的PriorityQueue。

PriorityQueue<E> pq = new PriorityQueue(PriorityQueue<E> c);

**6. PriorityQueue(SortedSet c) ** ：创建一个包含指定排序集合中元素的PriorityQueue。

PriorityQueue<E> pq = new PriorityQueue<E>(SortedSet<E> c);

**7. PriorityQueue(Comparator comparator)： ** 创建一个带有默认初始容量的PriorityQueue，其元素根据指定比较器排序。

PriorityQueue<E> pq = new PriorityQueue<E>(Comparator<E> c);

示例：

下面的示例说明了优先队列的以下基本操作：

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

// Java program to demonstrate the
// working of PriorityQueue
import java.util.*;
 
class PriorityQueueDemo {
   
      // Main Method
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
 
        // Adding items to the pQueue using add()
        pQueue.add(10);
        pQueue.add(20);
        pQueue.add(15);
 
        // Printing the top element of PriorityQueue
        System.out.println(pQueue.peek());
 
        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pQueue.poll());
 
        // Printing the top element again
        System.out.println(pQueue.peek());
    }
}

输出

10
10
15

PriorityQueue上的操作

让我们看一下如何执行Priority Queue类的一些经常使用的操作。

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

/* package whatever //不要在此处编写包名称 */
 
import java.util.*;
import java.io.*;
 
public class PriorityQueueDemo {
 
    public static void main(String args[])
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<3;i++){
            pq.add(i);
            pq.add(1);
        }
        System.out.println(pq);
    }
}

输出

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

我们不会得到排序的元素，因为PriorityQueue在内部进行排序。

/* package whatever //不要在此处编写包名称 */
 
import java.util.*;
import java.io.*;
   
public class PriorityQueueDemo {
   
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
   
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
   
        System.out.println(pq);
    }
}

输出

[For, Geeks, Geeks]

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

// Java程序，从优先队列中删除元素
 
import java.util.*;
import java.io.*;
 
public class PriorityQueueDemo {
 
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
 
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
 
        System.out.println("初始优先队列 " + pq);
 
          // 使用remove()方法
        pq.remove("Geeks");
 
        System.out.println("删除后 - " + pq);
 
        System.out.println("Poll方法 - " + pq.poll());
 
        System.out.println("最终优先队列 - " + pq);
    }
}

输出

初始优先队列 [For, Geeks, Geeks]
删除后 - [For, Geeks]
Poll方法 - For
最终优先队列 - [Geeks]

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

// Java程序，访问优先队列中的元素
import java.util.*;
 
class PriorityQueueDemo {
   
      // 主方法
    public static void main(String[] args)
    {
 
        // 创建一个优先队列
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println("优先队列：" + pq);
 
        // 使用peek()方法
        String element = pq.peek();
        System.out.println("已访问的元素：" + element);
    }
}

输出

优先队列： [For, Geeks, Geeks]
已访问的元素： For

4. 迭代优先队列： 有多种方法可以迭代优先队列。最流行的方法是将队列转换为数组，并使用for循环进行遍历。然而，队列也有内置的迭代器，可以用于遍历队列。

// Java程序，迭代优先队列中的元素
 
import java.util.*;
 
public class PriorityQueueDemo {
 
      // 主方法
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
 
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
 
        迭代器iterator = pq.iterator();
 
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}

输出

For Geeks Geeks

示例：

import java.util.PriorityQueue;
 
public class PriorityQueueExample {
 
    public static void main(String[] args) {
         
        //使用初始容量为10的优先队列
        PriorityQueue<Integer> pq = new PriorityQueue<>(10);
         
        //将元素添加到队列中
        pq.add(3);
        pq.add(1);
        pq.add(2);
        pq.add(5);
        pq.add(4);
         
        //输出队列
        System.out.println("优先队列: " + pq);
         
        //查看队列顶部元素的值
        System.out.println("查看: " + pq.peek());
         
        //删除队列顶部的元素
        pq.poll();
         
        //再次输出队列
        System.out.println("删除顶部元素后的优先队列: " + pq);
         
        //检查队列是否包含特定元素
        System.out.println("队列中是否包含3? " + pq.contains(3));
         
        //获取队列大小
        System.out.println("队列大小: " + pq.size());
         
        //删除队列中的所有元素
        pq.clear();
         
        //检查队列是否为空
        System.out.println("队列是否为空? " + pq.isEmpty());
    }
}

输出结果：

优先队列: [1, 3, 2, 5, 4]
查看: 1
删除顶部元素后的优先队列: [2, 3, 4, 5]
队列中是否包含3? true
队列大小: 4
队列是否为空? true

实时实例：

优先队列是一种数据结构，其中元素按优先级排序，优先级最高的元素出现在队列的前面。以下是一些实际情况中可以使用优先队列的实例：

任务调度： 在操作系统中，使用优先队列根据其优先级级别调度任务。例如，高优先级任务，如关键系统更新，可能会优先安排低优先级任务，如后台备份过程。
急诊室： 在医院急诊室中，根据病情的严重程度对患者进行分级，处于重症状态的患者首先接受治疗。使用优先队列可以管理医生和护士看到患者的顺序。
网络路由： 在计算机网络中，使用优先队列管理数据包的流动。高优先级数据包，如语音和视频数据，可能优先于低优先级数据包，如电子邮件和文件传输。
运输： 在交通管理系统中，优先队列可用于管理交通流量。例如，紧急车辆如救护车可能会优先于其他车辆，以确保它们能够快速到达目的地。
作业调度： 在作业调度系统中，可以使用优先队列管理作业的执行顺序。高优先级作业（如关键系统更新）可能会在低优先级作业（如数据备份）之前安排。
在线市场： 在在线市场中，优先队列可用于管理向客户交付产品。高优先级订单，如快递服务，可能优先于标准运输订单。

总的来说，优先队列是一种有用的数据结构，可在各种实际情况下根据优先级级别管理任务和资源。

PriorityQueue类中的方法

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

java.util.AbstractQueue中声明的方法

方法	描述
addAll(Collection c) \| 将指定集合中的所有元素添加到此队列中。 element() \| 检索但不删除此队列的头部。 remove() \| 检索并删除此队列的头部。 ### java.util.AbstractCollection中声明的方法方法 \| 描述 —\|— containsAll(Collection c)	如果此集合包含指定集合中的所有元素，则返回true。
isEmpty()	如果此集合不包含任何元素，则返回true。
toString()	返回此集合的字符串表示形式。

方法

描述

addAll(Collection c) | 将指定集合中的所有元素添加到此队列中。
element() | 检索但不删除此队列的头部。
remove() | 检索并删除此队列的头部。

### java.util.AbstractCollection中声明的方法

方法 | 描述
—|—
containsAll(Collection c)

如果此集合包含指定集合中的所有元素，则返回true。

isEmpty()

如果此集合不包含任何元素，则返回true。

toString()

返回此集合的字符串表示形式。

java.util.Collection接口中声明的方法

方法	描述
containsAll(Collection<?> c)	如果此集合包含指定集合中的所有元素，则返回true。
equals(Object o)	将指定对象与此集合进行比较以测试相等性。
hashCode()	返回此集合的哈希码值。
isEmpty()	如果此集合不包含任何元素，则返回true。
parallelStream()	返回可能使用此集合作为其源的并行流。
size()	返回此集合中的元素数。
stream()	返回此集合的顺序流作为其源。
toArray(IntFunction<T[]> generator)	使用提供的生成器函数分配返回的数组，返回包含此集合中所有元素的数组。

声明于java.util.Queue接口中的方法

方法	描述
peek()	检索但不删除此队列的头部，如果此队列为空，则返回null。
poll()	检索并删除此队列的头部，如果此队列为空，则返回null。