Java 中的优先级队列详细介绍

╰+哭是因爲堅強的太久メ 2023-09-24 22:39 3阅读 0赞

# 1.介绍 #

*  当应该根据优先级处理对象时，将使用 `PriorityQueu`。
 *  众所周知`Queue`是`遵循先进先出算法`的，但是有时候需要`按照优先级来处理队列中的元素`，这时候PriorityQueue就派上用场了。
 *  PriorityQueue 基于优先级堆。
 *  优先级队列的元素`根据自然顺序排序`，或者由`队列构造时提供的比较器排序`，具体取决于使用的构造函数  
    ![在这里插入图片描述][9499932157ae4e64a540170860f8c617.png]  
    在下面的优先级队列中，具有`最大 ASCII 值的元素将具有最高优先级`。  
    ![在这里插入图片描述][0d7476df01b449d890d2633b62f24ae4.png]

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 类`的方法。

## 构造函数： ##

1.  PriorityQueue()：创建一个具有默认初始容量 (11) 的 PriorityQueue，它根据元素的自然顺序对其元素进行排序  
    `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> pq = 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);`

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

*  `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 来获得已排序的元素。`

[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 循环遍历`。但是，队列还有一个`内置的迭代器`，可用于`遍历队列`。

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 类中的方法 #

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

[9499932157ae4e64a540170860f8c617.png]: https://img-blog.csdnimg.cn/9499932157ae4e64a540170860f8c617.png
[0d7476df01b449d890d2633b62f24ae4.png]: https://img-blog.csdnimg.cn/0d7476df01b449d890d2633b62f24ae4.png