优先队列

简介

许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或者不一定要一次就将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素。在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据结构类型叫做优先队列。

堆的算法

下面给出基于堆的优先队列。

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;        // 基于堆的完全二叉树
    private int N = 0;        // 存储与pq[1..N]中，pq[0]没有使用

    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

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

    public Key delMax() {
        Key max = pq[1];        // 从根结点得到最大元素
        exch(1, N--);            // 将其和最后一个结点交换
        pq[N + 1] = null;        // 防止对象游离
        sink(1);                // 恢复堆的有序性
        return max;
    }

    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;
    }

    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            exch(k/2, k);
            k = k/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;
        }
    }
}

下面是使用优先队列的多向归并。

public class Multiway {
    public static void merge(In[] streams) {
        int N = streams.length;
        IndexMinPQ<String> pq = new IndexMinPQ<String>(N);

        for (int i = 0; i < N; i++) {
            if (!streams[i].isEmpty()) {
                pq.insert(i, streams[i].readString());
            }
        }

        while(!pq.isEmpty()) {
            StdOut.println(pq.min());
            int i = pq.delMin();

            if (!streams[i].isEmpty()) {
                pq.insert(i, streams[i].readString());
            }
        }
    }

    public static void main(String[] args) {
        int N = args.length;
        In[] streams = new In[N];

        for (int i = 0; i < N; i++) {
            streams[i] = new In(args[i]);
        }

        merge(streams);
    }
}

堆排序

堆排序可以分为两个阶段。在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。

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);
    }
}