java 中 priorityqueue的使用

时间：2021-12-08 17:59:25

java.util
类 PriorityQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          java.util.PriorityQueue<E>
类型参数：
E - collection 中所保存元素的类型。
所有已实现的接口：
Serializable, Iterable<E>, Collection<E>, Queue<E> 
public class PriorityQueue<E>
extends AbstractQueue<E>implements Serializable 
 

一个基于优先级堆的*优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。 
 

此队列的头 是按指定排序方式确定的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。 



优先级队列是*的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。 
 

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。 
 

注意，此实现不是同步的。如果多个线程中的任意线程修改了队列，则这些线程不应同时访问 PriorityQueue 实例。相反，请使用线程安全的 PriorityBlockingQueue 类。 
 

实现注意事项：此实现为排队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；为 remove(Object) 和 contains(Object) 方法提供线性时间；为获取方法（peek、element 和 size）提供固定时间。 



此类是 Java Collections Framework 的成员。 
 

 

 



 
  从以下版本开始： 
 
 
 

   1.5 
 
 
 
 
  另请参见： 
 
 
 
 
  序列化表格 
 
 








构造方法摘要 
  




PriorityQueue()           使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。 
  




PriorityQueue(Collection<? extends E> c)           创建包含指定 collection 中元素的 PriorityQueue。 
  




PriorityQueue(int initialCapacity)           使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。 
  




PriorityQueue(int initialCapacity, Comparator<? super E> comparator)           使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。 
  




PriorityQueue(PriorityQueue<? extends E> c)           创建包含指定优先级队列元素的 PriorityQueue。 
  




PriorityQueue(SortedSet<? extends E> c)           创建包含指定有序 set 元素的 PriorityQueue。 
  





  
 




方法摘要 
  



 boolean 
   
add(E e)           将指定的元素插入此优先级队列。 
  



 void 
   
clear()           从此优先级队列中移除所有元素。 
  



 Comparator<? super E> 
   
comparator()           返回用来对此队列中的元素进行排序的比较器；如果此队列根据其元素的自然顺序进行排序，则返回 null。 
  



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



 Iterator<E> 
   
iterator()           返回在此队列中的元素上进行迭代的迭代器。 
  



 boolean 
   
offer(E e)           将指定的元素插入此优先级队列。 
  



 E 
   
peek()           获取但不移除此队列的头；如果此队列为空，则返回 null。 
  



 E 
   
poll()           获取并移除此队列的头，如果此队列为空，则返回 null。 
  



 boolean 
   
remove(Object o)           从此队列中移除指定元素的单个实例（如果存在）。 
  



 int 
   
size()           返回此 collection 中的元素数。 
  



 Object[] 
   
toArray()           返回一个包含此队列所有元素的数组。 
  




 
    

<T> T[] 
      

 
   
toArray(T[] a)           返回一个包含此队列所有元素的数组；返回数组的运行时类型是指定数组的类型。 
  




  
 




从类 java.util.AbstractQueue 继承的方法 
  



addAll, element, remove 
  





  
 




从类 java.util.AbstractCollection 继承的方法 
  



containsAll, isEmpty, removeAll, retainAll, toString 
  




  
 




从类 java.lang.Object 继承的方法 
  



clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait 
  




  
 




从接口 java.util.Collection 继承的方法 
  



containsAll, equals, hashCode, isEmpty, removeAll, retainAll 
  




  
 

 


构造方法详细信息 
  


PriorityQueue
 

public PriorityQueue()
 




   使用默认的初始容量（11）创建一个 
  PriorityQueue，并根据其 
  自然顺序对元素进行排序。 
  
 
 
 




 

PriorityQueue
 

public PriorityQueue(int initialCapacity)
 




   使用指定的初始容量创建一个 
  PriorityQueue，并根据其 
  自然顺序对元素进行排序。 
  
 
  


 
    参数： 
   
 
   
 
    initialCapacity - 此优先级队列的初始容量 
   
 
   
 
    抛出： 
   
 
   
 
    IllegalArgumentException - 如果 
    initialCapacity 小于 1 
   
 
  


 




 

PriorityQueue



public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator)
 




   使用指定的初始容量创建一个 
  PriorityQueue，并根据指定的比较器对元素进行排序。 
  
 
  


 
    参数： 
   
 
   
 
    initialCapacity - 此优先级队列的初始容量 
   
 
   
 
    comparator - 用于对此优先级队列进行排序的比较器。如果该参数为 
    null，则将使用元素的 
    自然顺序 
   
 
   
 
    抛出： 
   
 
   
 
    IllegalArgumentException - 如果 
    initialCapacity 小于 1 
   
 
  


 




 

PriorityQueue
 

public PriorityQueue(Collection<? extends E> c)
 




   创建包含指定 collection 中元素的 
  PriorityQueue。如果指定的 collection 是 
  SortedSet 的一个实例或者是另一个 
  PriorityQueue，那么此优先级队列将根据相同顺序进行排序。否则，此优先级队列将根据元素的 
  自然顺序进行排序。 
  
 
  


 
    参数： 
   
 
   
 
    c - collection，其元素要置于此优先级队列中 
   
 
   
 
    抛出： 
   
 
   
 
    ClassCastException - 如果根据优先级队列的排序规则无法比较指定 collection 中的各个元素 
   
 
   
 
    NullPointerException - 如果指定 collection 或任何元素为 null 
   
 
  


 





 

PriorityQueue
 

public PriorityQueue(PriorityQueue<? extends E> c)
 




   创建包含指定优先级队列元素的 
  PriorityQueue。此优先级队列将根据与给定优先级队列相同的顺序进行排序。 
  
 
  


 
    参数： 
   
 
   
 
    c - 优先级队列，其元素要置于此优先级队列中 
   
 
   
 
    抛出： 
   
 
   
 
    ClassCastException - 如果根据 
    c 的顺序无法比较 
    c 中的各个元素 
   
 
   
 
    NullPointerException - 如果指定优先级队列或任何元素为 null 
   
 
  


 




 

PriorityQueue
 

public PriorityQueue(SortedSet<? extends E> c)
 




   创建包含指定有序 set 元素的 
  PriorityQueue。此优先级队列将根据与给定有序 set 相同的顺序进行排序。 
  
 
  


 
    参数： 
   
 
   
 
    c - 有序 set，其元素将置于此优先级队列中 
   
 
   
 
    抛出： 
   
 
   
 
    ClassCastException - 如果根据有序 set 的顺序无法比较该有序 set 中的各个元素 
   
 
   
 
    NullPointerException - 如果指定有序 set 或任何元素为 null 
   
 
  


 


 


方法详细信息 
  


 
 

add
 

public boolean add(E e)
 




   将指定的元素插入此优先级队列。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    add 
   
 
   
 
    指定者： 
   
 
   

     接口 
    Queue<E> 中的 
    add 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractQueue<E> 中的 
    add 
   
 
  


 
 
 
  


 
    参数： 
   
 
   
 
    e - 要添加的元素 
   
 
   
 
    返回： 
   
 
   
 
    true（正如 
    Collection.add(E) 所指定的那样） 
   
 
   
 
    抛出： 
   
 
   
 
    ClassCastException - 如果根据优先级队列的顺序无法将指定元素与此优先级队列中当前元素进行比较 
   
 
   
 
    NullPointerException - 如果指定的元素为 null 
   
 
  


 




 
 

offer
 

public boolean offer(E e)
 




   将指定的元素插入此优先级队列。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Queue<E> 中的 
    offer 
   
 
  


 
 
 
  


 
    参数： 
   
 
   
 
    e - 要添加的元素 
   
 
   
 
    返回： 
   
 
   
 
    true（正如 
    Queue.offer(E) 所指定的那样） 
   
 
   
 
    抛出： 
   
 
   
 
    ClassCastException - 如果根据优先级队列的顺序无法将指定元素与此优先级队列中当前元素进行比较 
   
 
   
 
    NullPointerException - 如果指定元素为 null 
   
 
  


 




 

peek
 

public E peek()
 



 
  从接口 Queue 复制的描述 
 
 
 

   获取但不移除此队列的头；如果此队列为空，则返回 
  null。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Queue<E> 中的 
    peek 
   
 
  


 
 
 
  


 
    返回： 
   
 
   

     此队列的头；如果此队列为空，则返回 
    null 
   
 
  


 





 

remove
 

public boolean remove(Object o)
 




   从此队列中移除指定元素的单个实例（如果存在）。更确切地讲，如果此队列包含一个或多个满足 
  o.equals(e) 的元素 
  e，则移除一个这样的元素。当且仅当此队列包含指定的元素（或者此队列由于调用而发生更改），则返回 
  true。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    remove 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    remove 
   
 
  


 
 
 
  


 
    参数： 
   
 
   
 
    o - 要从此队列中移除的元素（如果存在） 
   
 
   
 
    返回： 
   
 
   

     如果此队列由于调用而发生更改，则返回 
    true 
   
 
  


 




 

contains
 

public boolean contains(Object o)
 




   如果此队列包含指定的元素，则返回 
  true。更确切地讲，当且仅当此队列至少包含一个满足 
  o.equals(e) 的元素 
  e 时，才返回 
  true。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    contains 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    contains 
   
 
  


 
 
 
  


 
    参数： 
   
 
   
 
    o - 要检查是否包含于此队列的对象 
   
 
   
 
    返回： 
   
 
   

     如果此队列包含指定元素，则返回 
    true 
   
 
  


 





 

toArray
 

public Object[] toArray()
 




   返回一个包含此队列所有元素的数组。数组元素没有特定的顺序。 
  
由于此队列并不维护对返回数组的任何引用，因而它将是“安全的”。（换句话说，此方法必须分配一个新数组）。因此，调用者可以随意修改返回的数组。 
 
  
此方法充当基于数组的 API 与基于 collection 的 API 之间的桥梁。 
 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    toArray 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    toArray 
   
 
  


 
 
 
  


 
    返回： 
   
 
   

     包含此队列所有元素的数组 
   
 
  


 




 
 

toArray
 

public <T> T[] toArray(T[] a)
 




   返回一个包含此队列所有元素的数组；返回数组的运行时类型是指定数组的类型。返回数组的元素没有特定的顺序。如果指定的数组能容纳队列，则将该队列返回此处。否则，将根据指定数组的运行时类型和此队列的大小分配一个新数组。 
  
如果指定数组能容纳队列，且有剩余空间（即数组比队列元素多），则紧跟在 collection 末尾的数组元素将被设置为 null。 
 
  
像 toArray() 方法一样，此方法充当基于数组 的 API 与基于 collection 的 API 之间的桥梁。进一步说，此方法允许对输出数组的运行时类型进行精确控制，在某些情况下，可以用来节省分配开销。 
 
  
假定 x 是只包含字符串的一个已知队列。以下代码可以用来将该队列转储到一个新分配的 String 数组： 
 
  
     String[] y = x.toArray(new String[0]);
注意， 
  toArray(new Object[0]) 和 
  toArray() 在功能上是相同的。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    toArray 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    toArray 
   
 
  


 
 
 
  


 
    参数： 
   
 
   
 
    a - 存储此队列元素的数组（如果该数组足够大）；否则，将为此分配一个具有相同运行时类型的新数组。 
   
 
   
 
    返回： 
   
 
   

     包含此队列所有元素的数组 
   
 
   
 
    抛出： 
   
 
   
 
    如果指定数组的运行时类型不是此队列每个元素的运行时类型的子类型 
   
 
   
 
    NullPointerException - 如果指定数组为 null 
   
 
  


 





 

iterator
 

public Iterator<E> iterator()
 




   返回在此队列中的元素上进行迭代的迭代器。迭代器并不以任意特定的顺序返回元素。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Iterable<E> 中的 
    iterator 
   
 
   
 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    iterator 
   
 
   
 
    指定者： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    iterator 
   
 
  


 
 
 
  


 
    返回： 
   
 
   

     在此队列的元素上进行迭代的迭代器 
   
 
  


 




 

size
 

public int size()
 



 
  从接口 Collection 复制的描述 
 
 
 

   返回此 collection 中的元素数。如果此 collection 包含的元素大于 
  Integer.MAX_VALUE，则返回 
  Integer.MAX_VALUE。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    size 
   
 
   
 
    指定者： 
   
 
   

     类 
    AbstractCollection<E> 中的 
    size 
   
 
  


 
 
 
  


 
    返回： 
   
 
   

     此 collection 中的元素数 
   
 
  


 




 

clear
 

public void clear()
 




   从此优先级队列中移除所有元素。此调用返回后队列为空。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Collection<E> 中的 
    clear 
   
 
   
 
    覆盖： 
   
 
   

     类 
    AbstractQueue<E> 中的 
    clear 
   
 
  


 
 
 




 

poll
 

public E poll()





 
  从接口 Queue 复制的描述 
 
 
 

   获取并移除此队列的头，如果此队列为空，则返回 
  null。 
  
 
 
 
 
 
  


 
    指定者： 
   
 
   

     接口 
    Queue<E> 中的 
    poll 
   
 
  


 
 
 
  


 
    返回： 
   
 
   

     队列的头，如果此队列为空，则返回 
    null 
   
 
  


 




 

comparator
 

public Comparator<? super E> comparator()
 




   返回用来对此队列中的元素进行排序的比较器；如果此队列根据其元素的 
  自然顺序进行排序，则返回 
  null。 
  
 
 
 
 
 
 
 
  


 
    返回： 
   
 
   

     用于对此队列进行排序的比较器；如果此队列根据其元素的自然顺序进行排序，则返回 
    null 
   
 
  


 

标签：
相关文章