Java 优先队列：非传统的队列

在本文中，我们学习优先队列，即 Java 类，它实现了 Queue 接口。程序员对常规 Queue 接口了解多少？首先，这个接口是基于 FIFO 原理，即“先进先出”。这就是常规的队列。你想从 McDrive 买杯咖啡吗？如果你的车第一个靠近窗户，你会比下一个司机先拿到咖啡。

Queue 接口声明

public interface Queue<E> extends Collection<E>

“什么是优先队列？”

什么是优先队列？首先，它是一个实现队列 Queue 的类，以便应对从后面插入一个元素和从头部删除一个元素的情况。不过，这并非一个普通的队列。Java 优先队列元素的顺序取决于元素的优先级。具有最高优先级的元素将被移到队列的头部。如果你删除（服务）排名最高的元素，第二个元素就会排到头部，获得咖啡。那如何确定优先级呢？根据该文档，优先队列的元素根据其自然顺序进行排序，或者根据构造队列时使用的 Comparator（取决于使用哪个构造方法）进行排序。优先队列基于优先级最小的堆。这意味着，如果队列元素是数字，则队列的第一个元素将是这些数字中的最小值。在阅读了这个定义之后，新手开始认为优先队列是线性排序的。也就是说，如果我们使用一个元素是自然数的队列，那么第一个元素是最小的，最后一个是最大的。这并不完全正确。为了理解优先队列实际是如何工作的及其功能，就需要弄清楚堆是如何工作的。我们稍后用一个例子来研究优先队列的内部结构。现在详细介绍下其外属性。

PriorityQueue 类构造方法和声明

PriorityQueue 类提供了 6 种不同的方法在 Java 中构造优先队列。

• PriorityQueue() - 具有默认初始容量 (11) 的空队列，根据元素的自然顺序对其进行排序。
• PriorityQueue(Collection c) - 包含指定集合中元素的空队列。
• PriorityQueue(int initialCapacity) - 具有指定初始容量的空队列，根据元素的自然顺序对其进行排序。
• PriorityQueue(int initialCapacity, Comparator comparator) - 具有指定初始容量的空队列，根据指定的 comparator 对其进行排序。
• PriorityQueue(PriorityQueue c) - 包含指定优先队列中元素的空队列。
• PriorityQueue(SortedSet c) - 包含指定排序集中元素的空队列。

Java 中的优先队列采用下列方式声明：

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

创建 PriorityQueue

现在创建整数优先队列。优先队列实施，Java 代码：

PriorityQueue<Integer> numbers = new PriorityQueue<>();

我们创建了一个不含参数的优先队列。在这种情况下，优先队列的头是队列的最小数。如果你移除队列头，下一个最小的元素将占用这个位置。因此你可以按升序从队列中移除元素。如有必要，你可以使用 Comparator 界面更改排序原则。

Java PriorityQueue 方法

PriorityQueue Java 类提供重要的方法添加、移除和检查元素。

将元素插入优先队列

• boolean add(object) 将指定元素插入优先队列。如果成功，则返回 true。如果队列已满，此方法抛出异常。
• boolean offer(object) 将指定的元素插入此优先队列。如果队列已满，此方法返回 false。

你可以使用两种加法运算，大多数情况下并无区别。这是一个初始化并将元素添加到优先队列的小例子。

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

输出是：

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

元素的顺序好像很奇怪，我们以后再说明。

从优先队列中检索和移除元素

• boolean remove(object) 从该队列中移除指定元素的单个实例（如果存在）。
• Object poll() 检索并移除该队列的头。如果队列为空，则返回 null。
• void clear() 从优先队列中移除所有元素。
• Object element() 检索此队列的头，但不将其移除。如果队列为空，则抛出 NoSuchElementException。
• Object peek() 检索此队列的头，但不将其移除。如果队列为空，则返回 null。

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

输出是：

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

正如你可能看到的，尝试使用 element() 方法输出空 Queue 的头会导致 NoSuchElementexception。

PriorityQueue Comparator

• Comparator comparator() 返回用于对队列中的元素进行排序的 comparator。如果队列根据其元素的自然顺序排序，则返回 null。

Java 优先队列，含 comparator 的例子

我们在上面的代码示例中使用了自然（升序）顺序，但有时我们应改变这一状况。下面是 Java 优先队列的例子，我们创建了自己的内部 comparator 类，该类实现了 Comparator 接口。我们的 comparator 将从最大到最小对元素排序。

import java.util.PriorityQueue;
import java.util.Comparator;

class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

输出是：

the head of Queue = 5
5
4
3
2
1

现在 Queue 的头不是最小元素，而是最大的元素，并且顺序被颠倒了。

使用 iterator 对 PriorityQueue 进行迭代

ProrityQueue 是 Collection 框架的一部分而且实施了 Iterable<> 接口。要迭代优先队列的元素，可以使用 iterator() 方法。下面是一个示例：

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;

class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

输出是：

1 2 4 5 3 

更多 PriorityQueue 方法

• boolean contains(Object o) 如果队列包含 o 元素，则返回 true。
• int size() 返回此队列中的元素数量。
• Object[] toArray() 返回包含此队列中所有元素的数组。

下面是一个示例：

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }

       System.out.println("our queue: " + priorityQueue);

       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));

       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

输出是：

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 定义

如果你打开优先队列 Java 8 文档，你会在此找到下一个定义：无边界优先队列基于优先堆。优先队列的元素根据其自然顺序进行排序，或者根据构造队列时使用的 Comparator（取决于使用哪个构造方法）进行排序。优先队列不允许使用 null 元素。依赖自然排序的优先队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。堆在这里很重要。它说明了优先队列元素排序的属性。

优先队列的工作原理：二叉堆

让我们从一个例子开始。我们创建两个实现 Queue 接口的对象。一个对象是 LinkedList，另一个是 PriorityQueue。这两个对象都包含 5 个整数元素（1、2、3、4 和 5），我们开始将元素从最大到最小放入我们的队列中。那么，第一个元素放入 5，以此放入 4、3、2，最后一个放入 1。然后，输出这两个列表来检查顺序。

Queue<Integer> queueL = new LinkedList<>();
    for (int i = 5; i > 0; i--) {
        queueL.add(i);
    }
    System.out.println("LinkedList Queue (FIFO): " + queueL);
    Queue<Integer> priorityQueue = new PriorityQueue<>();

    for (int i = 5; i > 0; i--) {
    priorityQueue.offer(i);
    }
    System.out.println("PriorityQueue: " + priorityQueue)

代码的运行结果如下所示：

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Linkedlist 顺序既可以预测，又可以理解。它根据 FIFO 原则进行排序。开始时是 5，因此此元素在一行中排在最前面，接着是 4 等。关于优先队列顺序，我们能知道些什么？文档说明优先队列的元素根据其自然顺序进行排序，或者根据构造队列时使用的 Comparator 进行排序。不过，该顺序对线性排序而言似乎并不是“自然而然”的。我们希望是 [1, 2, 3, 4, 5]，而不是 [1, 2, 4, 5, 3]。为了理解为何检索顺序是这样的，我们应该回忆一下基于堆的优先队列。什么是堆？这是一个基于二叉树的数据结构。堆的主要属性：每个父级的优先级大于其子级的优先级。提示一下，如果每个父级的孩子不超过两个，并且级别填充是从上到下（从同一级别从左到右），那么这样一棵树被称为完全二叉树。每次向二叉堆添加元素或从中移除元素时，二叉堆都会对自身进行重组。如果是最小堆，则最小元素转至根，与其插入的顺序无关。优先队列就是基于此最小堆。这意味着，如果队列元素是数字，则队列的第一个元素将是这些数字中的最小值。如果删除根，下一个最小元素就变成根。

我们看看例子。

第 1 步。我们将“5”放入优先队列。它便成为根。
第 2 步。我们将“4”添加到优先队列。4 <5，因此，新元素应高于旧元素。4 成为根，5 为左子树。现在 Java 中的数据结构为 [4, 5]
第 3 步。我们添加“3”。此暂时变成根 (4) 的右子树。不过，3 < 4，因此我们应提升其级别。将 3 和 4 交换。现在，我们获得一个结构，例如 [3, 5, 4]
第 4 步。我们添加“2”。它会变成左子树为 5。2<5，一次两者进行交换。2 变为 3 的左子树，2 < 3，因此还要进行一次交换过程。现在，我们获得一个结构 [2,3,4,5]
第 5 步。我们添加“1”。右子树 3 变为左子树 2，然后 1 到达根部。最终的数据结构：[1,2,4,5,3] 移除过程从根开始，引发相反的过程。因此，首先将 1 作为根，然后分别是将 2、3、4，最后是 5 作为根。 这是使用移除操作 poll() 的原因

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

我们得到线性“排序”结果：

1
2
3
4
5

因此优先队列对于某些运算可能是有效的。它需要 O(log N) 长时间插入和删除每个元素，并且可以在 O(1) 中获得最小元素。这是个完整的例子：

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

理解优先队列基于二叉堆很重要，因此它们不会以线性排序顺序保持元素。从根到叶的每一条路都是有序的，但从根开始的不同路却不是有序的。这意味着你可以非常快地获得队列的最小元素。

你应该了解的有关优先队列的信息。简短列表

• 优先队列不允许使用 NULL 对象。
• 你只能将可比较的对象添加到 PriorityQueue。
• 优先队列是以最小堆的形式构建的，这是一种二叉树。最小元素是根。优先队列的对象默认按自然顺序排序。
• 如果需要自定排序，可以使用 Comparator。
• PriorityQueue 在线程级别并不安全，因而最好在并发环境中使用 PriorityBlockingQueue。
• PriorityQueue 为 add 和 poll 方法提供的时间为 O(log(n))，获取最小元素的时间为 O(1)。