概述
优先队列不同于普通队列，优先队列不再仅遵循“先进先出”规则，当删除元素时，优先队列总是倾向于删除优先级最高的元素。其支持两种操作：删除最大元素和插入元素。
应用场景：模拟系统、任务调度、数值计算。
延拓：堆排序
范型优先队列API如下：
实现方法
总的来说，和排序算法类似，实现优先队列有数组和链表两种实现结构；每种数据结构实现又可以分别按照插入时保持队列有序和取出时找到最大元素两种思路进行设计。具体方法代码如下（以插入时保持队列有序的数组实现和取出最大元素的链表实现为例）：
插入时保持队列有序的数组实现：
public class PQueueSortedArray<Key extends Comparable<Key>> {
private Key[] a;
private int size;
// PQueueSortedArray() 创建一个空优先队列
public PQueueSortedArray() {
a = (Key[]) new Object[1];
}
// PQueueSortedArray(int max) 创建一个大小为max的优先队列
public PQueueSortedArray(int max) {
a = (Key[]) new Object[max];
}
// PQueueSortedArray(key[] inputA) 用inputA中的元素创建一个优先队列
public PQueueSortedArray(Key[] inputA) {
a = inputA;
int N = a.length; // 数组长度
for (int i = 0; i < N; i++) { // 插入排序
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
size = inputA.length;
}
// insert(Key item) 想优先队列中插入一个元素
public void insert(Key item) {
int N = a.length; // 数组长度
if (size == N) resize(2 * N);
a[size] = item;
for (int i = size++; i > 0 && less(a[i], a[i - 1]); i--) {
exch(a, i, i - 1);
}
}
// max() 返回最大元素
public Key max() {
return a[size - 1];
}
// delmax() 删除并返回最大元素
public Key delmax() {
return a[--size];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void resize(int max) {
Key[] temp = (Key[]) new Object[max];
for (int i = 0; i < size; i++) {
temp[i] = a[i];
}
a = temp;
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static boolean isSorted(Comparable[] a) { // 测试数组元素是否有序
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1])) return false;
return true;
}
}
取出最大元素的链表实现：
public class PQueueUnsortedLink<Key extends Comparable<Key>> {
private int size;
private Node first;
private class Node {
Key item;
Node next;
}
public PQueueUnsortedLink() {
first = new Node();
}
public PQueueUnsortedLink(int max) {
first = new Node();
}
public PQueueUnsortedLink(Key[] inputA) {
first = new Node();
size = inputA.length;
for (int i = 0; i < inputA.length; i++) {
Node oldfirst = first;
first = new Node();
first.item = inputA[i];
first.next = oldfirst;
}
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public Key max() {
assert !isEmpty();
Key max = first.item;
Node temp = first;
while (temp.next.item != null) {
if (temp.next.item.compareTo(max) > 0) max = temp.next.item;
temp = temp.next;
}
return max;
}
public Key delmax() {
assert !isEmpty();
Key max = first.item;
Node temp = first;
int count = 0; // 计数器
int maxAdress = 0; // 记录最大元素出现位置
while (temp.next.item != null) {
count++;
if (temp.next.item.compareTo(max) > 0) {
max = temp.next.item;
maxAdress = count;
}
temp = temp.next;
}
// 将两部分链表拼接在一起
temp = first;
for (int i = 0; i < maxAdress - 1; i++) {
temp = temp.next;
}
if (maxAdress == 0 && size > 1) first = first.next;
else if (maxAdress == size - 1) temp.next = new Node();
else temp.next = temp.next.next;
size--;
return max;
}
public void insert(Key item) {
Node temp = first;
first = new Node();
first.item = item;
first.next = temp;
size++;
}
}
优化我们的实现：堆排序
一些定义
堆有序：在一棵二叉树中，每个结点均大于它的子结点。 完全二叉树：一个二叉树，除最后一层外，其他各层的结点都达到最大个数，并且最后一层的所有结点都连续集中在二叉树的最左边。 二叉堆：堆有序的完全二叉树，并且树中的每一个元素按照从左到右、从上到下、从大到小的顺序在数组中储存（不使用数组的第一个位置）
可以容易地推断出在一个二叉堆中，一个位置为k的结点的父结点位置是 $k/2$ ，其子结点位置是 $2k$ 或 $2k+1$。
算法实现
和基本排序算法一样，我们依然需要两个辅助算法完成元素的比较和交换操作，不过这次因为所有元素都储存在同一个数组中，因此我们的代码可以更加简化：
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key k = pq[i];
pq[i] = pq[j];
pq[j] = k;
}
排序分别采用自底向上排序swim(int k)和自顶向下排序sink(int k)实现
// 自顶向下排序
private void sink(int k) {
while (k * 2 <= size) {
if (k * 2 == size) {
if (less(k, k * 2)) exch(k, k * 2);
break;
}
int ma = less(k * 2, k * 2 + 1) ? k * 2 + 1 : k * 2;
if (less(k, ma)) exch(k, ma);
k = k * 2;
}
}
// 自底向上排序
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k / 2, k);
k = k / 2;
}
}
整个算法实现代码如下：
public class PQueueMaxStack<Key extends Comparable<Key>> {
private Key[] pq;
private int size;
public PQueueMaxStack(int max) {
pq = (Key[]) new Comparable[max];
}
// 自顶向下排序
private void sink(int k) {
while (k * 2 <= size) {
if (k * 2 == size) {
if (less(k, k * 2)) exch(k, k * 2);
break;
}
int ma = less(k * 2, k * 2 + 1) ? k * 2 + 1 : k * 2;
if (less(k, ma)) exch(k, ma);
k = k * 2;
}
}
// 自底向上排序
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k / 2, k);
k = k / 2;
}
}
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key k = pq[i];
pq[i] = pq[j];
pq[j] = k;
}
public void insert(Key item) {
pq[++size] = item;
swim(size);
}
public Key delMax() {
Key item = pq[1];
exch(1, size);
sink(1);
return item;
}
public Key max() {
return pq[1];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
复杂度分析
由于二叉树的实现策略，对于一个大小为N的数组，每次向下或向上排序的复杂度均为 $O(lgN)$ ，max()和delMax()只需要一次操作就可以找到最大的元素。
延伸：堆排序
上述实现的优先队列只能保证二叉树的层级之间（纵向）是有序的，而并没有完成整个数组上的排序（横向），因此我们在此基础上进行扩展，即实现一种全新的排序算法：堆排序：
- 首先用上述算法保证数组的堆有序（纵向）；
- 循环完成下面的操作，直到数组完全有序： (1) 将根结点和无序堆末尾结点交换； (2) 将数组拆分成有序堆和无序堆； (3) 在无序堆中进行自顶向下排序。
该算法复杂度是 $O(NlgN)$ :
public class StackSort {
public static void sort(Comparable[] a) {
// 首先保证堆有序
for (int i = (a.length - 1) / 2; i > 0; i--) {
sink(a, i, a.length - 1);
}
// 其次完成整个数组的排序
for (int i = a.length - 1; i > 1; i--) {
exch(a, 1, i);
sink(a, 1, i - 1);
}
}
// 自顶向下排序
private static void sink(Comparable[] a, int k, int ma) {
while (k * 2 <= ma) {
if (k * 2 == ma) {
if (less(a, k, k * 2)) exch(a, k, k * 2);
break;
}
int ex = less(a, k * 2, k * 2 + 1) ? k * 2 + 1 : k * 2;
if (less(a, k, ex)) exch(a, k, ex);
k = k * 2;
}
}
private static boolean less(Comparable[] a, int i, int j) {
return a[i].compareTo(a[j]) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable k = a[i];
a[i] = a[j];
a[j] = k;
}
}