Java PriorityQueue

当对象需要根据优先级被处理时，就会用到PriorityQueue。众所周知，队列遵循先入先出的算法，但有时需要根据优先级来处理队列中的元素，这时PriorityQueue就发挥作用了。

PriorityQueue是基于优先级堆的。优先级队列的元素根据自然排序，或者通过队列构造时提供的比较器进行排序，这取决于使用的构造器。

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

声明

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

where E is the type of elements held in this queue

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

关于优先级队列的 几个要点如下。

• PriorityQueue不允许出现null。
• 我们不能创建一个没有可比性的对象的PriorityQueue。
• PriorityQueue是非绑定队列。
• 这个队列的头部是相对于指定的排序而言的最小元素。如果多个元素在最小值上并列，那么头部就是这些元素中的一个–并列关系被任意打破。
• 由于PriorityQueue不是线程安全的，java提供了PriorityBlockingQueue类，实现了BlockingQueue接口，可以在java多线程环境中使用。
• 队列检索操作轮询、删除、窥视和元素访问队列头部的元素。
• 它为添加和轮询方法提供了O(log(n))时间。
• 它继承了 AbstractQueue 、 AbstractCollection 、 Collection 和 Object 类的方法。

构造函数

1.PriorityQueue(): 创建一个具有默认初始容量（11）的PriorityQueue，根据元素的自然排序进行排序。

PriorityQueue pq = new PriorityQueue()。

**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。

// 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的操作

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

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

/*package whatever //do not write package name here */
  
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 //do not write package name here */
  
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 program to remove elements
// from a PriorityQueue
  
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("Initial PriorityQueue " + pq);
  
          // using the method
        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.访问元素： 由于队列遵循先入先出原则，我们只能访问队列的头部。要访问优先队列中的元素，我们可以使用peek()方法。

// Java program to access elements
// from a PriorityQueue
import java.util.*;
  
class PriorityQueueDemo {
    
      // Main Method
    public static void main(String[] args)
    {
  
        // Creating a priority queue
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println("PriorityQueue: " + pq);
  
        // Using the peek() method
        String element = pq.peek();
        System.out.println("Accessed Element: " + element);
    }
}

输出

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

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

// Java program to iterate elements
// to a PriorityQueue
  
import java.util.*;
  
public class PriorityQueueDemo {
  
      // Main Method
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
  
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
  
        Iterator iterator = pq.iterator();
  
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}

输出

For Geeks Geeks 

PriorityQueue类中的方法

类java.util.AbstractQueue中声明的方法

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

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

应用:

• 实现Dijkstra的和Prim的算法。
• 在K次否定后使数组总和最大化