Ex2_2_33 索引优先队列

2.4.4.7/Ex2_2_33/34 索引优先队列

很多时候,数据输入流有多个,且数量巨大(10亿个),使用索引可以确定不同输入流,使用优先队列可以确保无论输入多长都可以读入并排序,二者结合即索引优先队列

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
    /*
   本例使用merge(),基于索引优先队列,将作为命令行输入的多
   行字符串(字符串本身升序排好),归并为为一行有序的输出.
    */
public class IndexMinPQ<Key extends Comparable<Key>> {
    private Key[] keys;//存放原始数据,顺序不变
    private int[] pq;//存放索引的二叉堆,从1开始
    private int[] qp;//存放索引的逆序,qp[pq[i]] = pq[pq[i]] = i;
    private int N;//PQ中元素数量
    /*
    ----------constructor and Helpers-----------
     */
    public IndexMinPQ(int maxN){
        keys = (Key[]) new Comparable[maxN+1];
        pq = new int[maxN+1];
        qp = new int[maxN+1];
        //当索引i不在队列中,令qp[i] = -1
        for (int i =0; i<= maxN; i++) qp[i] = -1;
    }
    public boolean isEmpty(){ return N == 0;}
    public int size(){ return N;}
    //通过返回对索引的查找结果确定是否包含元素
    public boolean contains(int k){ return qp[k] != -1; }
    /*
    ----------major function-----------
     */
    public void insert(int pri, Key key){
        N++;
        pq[N] = pri;//保存索引
        qp[pri] = N;//保存pq的逆序
        keys[pri] = key;
        swim(N);
    }
    public Key min(){ return keys[pq[1]]; }
    public int delMin(){
        int indexOfMin = pq[1];
        exch(1, N--);
        sink(1);
        keys[pq[N+1]] = null;
        qp[pq[N+1]] = -1;
        return indexOfMin;//返回indexOfMin,确定输入流
    }
    private void change(int pri, Comparable key){
        keys[pri] = key;
        int index = qp[pri];
        swim(index);
        sink(index);
    }
    public void delete(int pri){
        int index = qp[pri];
        exch(index, N--);
        swim(index);
        sink(index);
        keys[pri] = null;
        qp[pri] = -1;
    }
    //此处使用large(),构造小顶堆
    private boolean larger(int i, int j){
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }
    private void exch(int i, int j){
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
    public void swim(int k){
        while (k > 1 && larger(k/2, k)){
            exch(k/2, k);
            k = k/2;
        }
    }
    public void sink(int k) {
        while (k * 2 <= N) {
            int j = k * 2;
            if (larger(j, j + 1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
            if (!larger(k, j)) break;//比较父子大小
            exch(k, j);
            k = j;
        }
    }
    public static void merge(In[] streams){
        int N = streams.length;
        IndexMinPQ<String> pq = new IndexMinPQ<>(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());
        }
    }
    /*
    -----------test function-----------
     */
    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);
    }
}

算法理解:

关于索引优先队列:

在一般的优先队列中,我们只能通过delMax()访问最大元素,无法直接访问队列中其他元素进行更新或删除,要是建立一个映射关系,让队列中第k个元素操纵着原始数据,队列中针对这种关系排序即可,不改变原始数据结构.实现这种映射控制需要索引(priority)

上述算法中,keys[]即为原始数据结构,只有change()或delete()会改变其中元素,排序对其无影响;pq[]为索引队列,里面依据keys[]中元素堆有序保存了对应的索引,pq[1]即保存了最小元素的索引,比如pq[1]=3,说明keys[3]的元素最小

当要更新元素时,如将keys[5]元素改变,再去维护pq[i]的值,但除非遍历pq[],无法获悉哪个元素pq[i]保存了5,因此必须再添加一个数组,保存与对象相关的队列数组元素下标,qp[pq[i]]=pq[qp[i]]=i;,假如qp[5] = 3,则pq[3]中保存了索引5,这时恢复pq有序,对应恢复qp有序.

关于归并输入流:

假设命令行参数传入m1.txt,m2.txt,m3.txt三个文件,每个文件中有一列升序的字符串,则main函数stream[]是含有N=3的数组,则merge()一开始读取stream[]三个流元素的首个字符串,三个字符串构成索引优先队列,然后delMin(),输出并删除三者最小,再补充删去元素索引对应的下个字符串,知道所有流下的所有字符串都被输出并删除,达成归并不同流并排序的目的.

图示:

算法分析:

大小N的索引优先队列,插入insert(),改变优先级change(),删除delete(),删除最小元素delMin()操作所需比较次数和logN成正比

证明:由堆中所有路径最长为~lgN,可得

N个元素的堆索引优先队列不同操作最坏情况下成本

Review:

1. 索引pri是指定key[]中的某个位置,实际元素即key[pri],pq[i]==pri代表此索引堆有序后在堆中第i处,为方便找出key[pri]的索引在pq[]哪个位置,引入qp[],使得qp[pri]=qp[pq[i]]=i;
2. sink()中if (larger(j, j+1) && j < N) j++构造小顶堆找子结点较小者,构造大顶堆找子结点较大者
3. 三个边界取等问题

• 构造函数for (int i=0; i <= maxN; i++),因为contains通过qp[pri]是否为-1判断,qp[maxN]即保存key[maxN]的索引倒序
• swim()while (k > 1 && larger(k/2, k)),若k>=1,k=1时操作空元素pq[0]
• sink()while (k*2 <= N),当k恰为2次幂时,层数加一,需要判断下沉.

1. insert()在末尾操作只需swim(),change()和delete()涉及中间操作要先swim()在sink()
2. merge()实现不唯一

private static void merge(In[] streams){
        int N = streams.length;
        IndexMinPQ pq = new IndexMinPQ(N);
        //读入初始三个值
        for (int i = 0; i < N; i++)
            if (! streams[i].isEmpty())
                pq.insert(streams[i].readString(), i);
        StdOut.println(pq.showMin());
        int i = pq.delMin();
        while (!streams[i].isEmpty()){
            pq.insert(streams[i].readString(), i);
            StdOut.println(pq.showMin());
            i = pq.delMin();
        }
    }