算法笔记：优先权队列

优先权队列

Stack. Remove the item most recently added.

Queue. Remove the item least recently added.

Randomized queue. Remove a random item.

Priority queue. Remove the largest (or smallest) item

优先权队列，与队列不同(first in, first out)，优先权队列每次取出的是队列中值最大或最小的元素。

优先权队列API

这个优先权队列的API还是十分好理解的，无非就是插入元素和删除元素。

优先权队列初等实现

我们先看一下这种队列不是很好的实现方法。

public class UnorderedMaxPQ<Key extends Comparable<Key>>
{
 private Key[] pq; // pq[i] = ith element on pq
 private int N; // number of elements on pq
 public UnorderedMaxPQ(int capacity)
 { pq = (Key[]) new Comparable[capacity]; }
 public boolean isEmpty()
 { return N == 0; }
 public void insert(Key x)
 { pq[N++] = x; }
 public Key delMax()
 {
 int max = 0;
 for (int i = 1; i < N; i++)
 if (less(max, i)) max = i;
 exch(max, N-1);
 return pq[--N];
 }
}

显然买这种实现方法对于删除最大值需要O(n)的算法复杂度，这显然达不到我们的预期，我们要找到更好的方法。

这个时候，一个新的数据结构二叉堆，闪亮登场。

二叉堆

二叉堆可以看作是一棵二叉树，并且它是近似完全平衡的（除了最后一层节点），父节点不小于子节点（最大堆）

二叉堆的一些表示如下：

使用数组来表示二叉堆。

节点从数组下标为1的位置开始(不使用0)，对于下标为k的点，其父节点为k/2，子节点为2k和2k+1.

二叉堆具体使用方法

首先我们定义两种操作

(1)上浮

private void swim(int k)
{
 while (k > 1 && less(k/2, k))
 {
 exch(k, k/2);
 k = k/2;
 }
}

如果子节点比父节点大，那么把子节点和父节点交换，也就是让子节点上浮。

(2) 下沉

private void sink(int k)
{
 while (2*k <= N)
 {
 int j = 2*k;
 if (j < N && less(j, j+1)) j++;
 if (!less(k, j)) break;
 exch(k, j);
 k = j;
 }
}

同理，父节点比子节点小，让子节点和父节点交换，即让父节点下沉。

接下来我们来实现具体的应用。

(1) 插入

public void insert(Key x)
{
 pq[++N] = x;
 swim(N);
}

如果所示，我们只要把要插入的元素放到最后，然后使用上浮操作，即可完成。

(2) 删除最大值

public Key delMax()
{
 Key max = pq[1];
 exch(1, N--);
 sink(1);
 pq[N+1] = null;
 return max;
} 

将最大值和最小值交换，通过N--把最大值删掉，然后通过上浮操作调整堆。

完整实现如下：

public class MaxPQ<Key extends Comparable<Key>>
{
 private Key[] pq;
 private int N;
 public MaxPQ(int capacity)
 { pq = (Key[]) new Comparable[capacity+1]; }
 public boolean isEmpty()
 { return N == 0; }
 public void insert(Key key)
 public Key delMax()
 { /* see previous code */ }
 private void swim(int k)
 private void sink(int k)
 { /* see previous code */ }
 private boolean less(int i, int j)
 { return pq[i].compareTo(pq[j]) < 0; }
 private void exch(int i, int j)
 { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }
}

堆排序

这个在思想上就很简单了，每次我们都能拿出最大的那个元素，这样子把元素拿完，我们就得到了从大小的排序序列。

public class Heap
{
 public static void sort(Comparable[] a)
 {
 int N = a.length;
 for (int k = N/2; k >= 1; k--)
 sink(a, k, N);
 while (N > 1)
 {
 exch(a, 1, N);
 sink(a, 1, --N);
 }
 }
 private static void sink(Comparable[] a, int k, int N)
 { /* as before */ }
 private static boolean less(Comparable[] a, int i, int j)
 { /* as before */ }
 private static void exch(Comparable[] a, int i, int j)
 { /* as before */ }
}

算法复杂度

各种排序算法的比较