索引优先队列

Posted on

《算法 第四版》索引优先队列有感…

重点理解示意图!

一、优先队列

使用二插堆, 利用swim和sink操作很容易实现最小优先队列和最大优先队列(取决于比较方式), 同时也可以顺便实现堆排序算法, 具体细节在此按下不表, 请自行搜索学习。

二、索引优先队列

1、前言

《算法 第四版》提到了索引优先队列这个数据结构, 该数据结构不仅有优先队列的快速操作, 同时还能方便地利用索引自由地进行更多的操作, 比如返回最大(最小)元素的索引, 修改某个索引对应的元素, 删除某个索引的元素或是最大(最小)元素等等. 利用该数据结构我们可以方便地解决很多问题. 但是, 该数据结构的实现往往很容易让人迷惑, 所以, 我们用最大索引优先队列为例, 尽可能地让读者对此有清晰的理解。

2、数据结构

索引优先队列主要由三个数组实现, 其中两个索引数组, 一个元素数组(容器), 我们把它们分别叫做qp[], pq[], items[]数组. pq[]数组索引items[], qp[]数组索引pq[], 我们维护的优先队列实际上是对pq[]数组的维护. 我们首先用插入操作举个例子,先来看看它的代码:

    public void insert(int k, Item v) {
        N++;
        qp[k] = N;
        pq[N] = k;
        items[k] = v;
        swim(N);
    }

一时看不懂没关系,继续看下去,待会再返回来看代码.我们可以看到,我们对Item元素的索引k实际上就是qp[]和items[]数组的下标,对没有索引的元素,我们会将qp[]数组对应下标的值置-1表示没有这个索引值.

    public IndexMaxPQ(int max) {
        pq = new int[max + 1];
        qp = new int[max + 1];
        items = (Item[]) new Comparable[max + 1];
        for(int i = 0; i <= max; i++) {
            qp[i] = -1; // 表示该索引没有item
        }
    }

我们一旦使用了索引k,那么要么改变该索引的元素,要么删除该索引和对应的元素,否则他们是固定不变的(实际上,items[]数组不变,qp[]数组是会改变的,因为它是用来索引pq[]数组的,这点我们下面会更清楚地讲解明白). 然后我们可以看到我们使用了一个优先队列中很重要的函数swim保持其堆有序,在此处的作用也和优先队列中的一样,不过他所使用的exchange函数有很大的不同.我们再来看看下面的图,就能更清楚这三个数组之间的关系了:

在这里我们可以看到, 对于任意的1 <= k <= N,pq[qp[k]]=qp[pq[k]] = k(这也是书上的结论),qp[]和items[]数组关于pq[]数组对称. 我们使用swim和sink函数维护堆有序性的时候,实际上也是利用这种关系来实现的.维护pq[]数组时,我们利用pq[]指向的Item元素进行比较,决定是否上浮或下沉,然后重新修改pq[]和qp[]指向的元素,swim和sink函数的操作对象是pq[]数组.我们来看一看exchange函数和进行比较的less函数:

    private boolean less(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    private void exch(int i, int j) {
        int k1 = pq[i];
        int k2 = pq[j];
        qp[k1] = j;
        pq[j] = k1;
        qp[k2] = i;
        pq[i] = k2;
    }

less函数就不多解释了,我们来看一看exchange函数.我们首先保存pq[]数组中i,j指向的元素的索引,因为他们是不改变的,然后修改我们qp[]数组和pq[]数组相应的索引值实现了交换操作,这个操作通过上面的示意图可以更直观的看出来. 我们一旦理解了这个过程,其他的东西便可迎刃而解了: 1、最大(最小)值或者索引,可以直接通过pq[1]得出; 2、修改某个索引元素,只需要修改items[]数组对应索引下标的元素,然后重新调整对应的pq[]数组使其堆有序(修改后的元素可能打破这个规则); 3、删除最大(最小)或者某个索引值对应元素,我们只需要像优先队列一样,将该索引指向的pq[]数组元素与最后一个元素交换后减小堆的大小,然后利用swim和sink函数调整交换后的堆使其堆有序.

3、完整代码(以最大优先队列为例)

import java.lang.Comparable;

public class IndexMaxPQ<Item extends Comparable<Item>> {
    private int[] pq;
    private int[] qp;
    private Item[] items;
    private int N = 0;

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

    private void sink(int k) {
        while(k*2 <= N) { // 有子节点才继续
            int j = k*2;
            if(j+1 <= N && less(j, j+1)) j += 1;

            if(!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    private boolean less(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    private void exch(int i, int j) {
        int k1 = pq[i];
        int k2 = pq[j];
        qp[k1] = j;
        pq[j] = k1;
        qp[k2] = i;
        pq[i] = k2;
    }

    public IndexMaxPQ(int max) {
        pq = new int[max + 1];
        qp = new int[max + 1];
        items = (Item[]) new Comparable[max + 1];
        for(int i = 0; i <= max; i++) {
            qp[i] = -1; // 表示该索引没有item
        }
    }

    public boolean contains(int k) {
        return qp[k] != -1;
    }

    public void insert(int k, Item v) {
        N++;
        qp[k] = N;
        pq[N] = k;
        items[k] = v;
        swim(N);
    }

    public void change(int k, Item v) {
        items[k] = v;
        swim(qp[k]);
        sink(qp[k]);
    }

    public int delmax() {
        int k = pq[1];
        exch(1, N--);
        sink(1);
        items[pq[N+1]] = null;
        qp[pq[N+1]] = -1;
        return k;
    }

    public void delete(int k) {
        exch(qp[k], N--);
        swim(qp[k]);
        sink(qp[k]);
        items[pq[N+1]] = null;
        qp[pq[N+1]] = -1;
    }

    public int maxIndex() {
        return pq[1];
    }

    public Item max() {
        return items[pq[1]];
    }

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

    public int size() {
        return N;
    }

    public static void main(String[] args) {
    }
}