堆的几个应用

简介

    关于堆和PriorityQueue的思想和实现，前面的几篇文章我都有详细的描述，比如堆排序的实现和PriorityQueue的实现。在这些实现的基础上，实际上还有很多实际应用中的变体，比如在某些情况下我们会用到多路归并算法，还有一个就是在一些图算法的应用场景里，我们需要一个动态保持最小若干元素的集合。这些东西都离不开堆的思想和它们的应用。这里，我们针对这些变体的实现思路做一个详细的讨论。

 

在讨论我们这个具体应用的数据结构之前，让我们先看看以前一些实现里所面临的问题。

 

存在的几个问题

多路归并算法

    在前面的一些文章里，我们提到。针对一些大数据文件的处理和归并，少不了要使用多路归并算法来实现。在多路归并算法里，它的基本思路如下：

1. 首先输入是一个输入流数组比如In[]，假设长度为k。 从这k个流里每个都取一个元素来构建一个大小为k的最小堆。

2. 每次取出最小堆里顶端的元素，然后再从最顶端元素对应流里取出下一个元素来加入到堆中，并调整堆。如果最小元素对应的流已经读取空了则直接调整堆。

3. 重复过程2直到所有流元素都处理完毕。

    在我们具体实现的时候，可能就会有这么一系列的问题。首先一个就是我们给定的输入流里，每个流是对应着这个数组里的某个索引的。但是我们建的这个堆是要经常做动态调整，比如说我们前面流In[1]里的元素比In[2]里读出来的元素大，那么它们就需要交换位置。在堆里交换位置之后，我们怎么能让In[1]的这个元素和In[1]这个流对上号呢？所以，我们就需要知道，当我们给定流数组里某个流的时候，比如In[2]，我们需要知道它所对应的那个读出的元素在堆里的位置。

    另外，假设我们堆经过一系列的排序调整，最终得到最小的元素是堆顶的那个。它在堆里对应的索引根据我们的实现可能是queue[0]或者queue[1]。按照前面的过程，我们需要将它移除，同时再找到它对应的流。因为还要从这个对应的流里去读后续的内容来加入到堆里。那么，我们怎么去找呢？所以，这里很可能也需要有一个对应的关系。

 

Dijkstra算法

    在我前面的一篇文章里有提到过该算法。这个算法有一个思路就是从一个源节点开始根据关联关系保存一个到该节点距离的最小堆，每次当有新的边和节点加入进来的时候，要根据新加入节点和原有节点的距离以及原来推算的节点间距离进行比较，然后碰到合适的距离要更新整个堆。这就好比是更新了堆中间的某个元素。只是相对来说是让一个节点的元素变得更小了。默认的优先队列里并没有更新元素值然后自动调整堆的方法支持。同时，也和前面一样的问题，我们新加入元素和距离更新之后，会调整整个堆的大小。这里对应的堆元素是对应到哪个节点呢？

    所以，根据前面这两个部分反映出来的问题，我们至少要保证修改后的堆结构要支持一下几个功能。

1. 根据堆里的元素索引能找到对应的源输入流索引。

2. 根据对应的输入流索引可以找到对应的堆元素索引。

3. 可以动态调整堆里任意元素的值并进行调整，而不仅仅只是堆顶和新加入到堆尾的元素。

    于是，有了这几个需要增强的点，我们来考虑如下的增强堆结构：

 

IndexMinPQ

    这是我们要介绍的变体，当然，一开始说这个东西的时候我们可能会有点疑惑，这个数据结构到底是什么样的呢？它和我们常用的PriorityQueue有什么区别呢？我们这里就一一比对过来。

 

结构

    我们传统的堆结构本质上是一个数组，它只是以一种二叉树的样式来处理和访问。所以假设我们有如下的二叉树：

     它对应的存储数组则如下图所示：

     根据我们前面讨论的问题描述，对于一个堆来说，它里面的元素会动态调整，而对应的数据流却是相对固定的，所以我们需要有一个表来保存它们之间的映射关系。

 于是我们这里就有一个表pq， 其中pq定义为int[]的数组，它保存的是指向具体堆元素的索引。它是一个形式上的最小堆，不过它里面的元素只是索引而已。具体参加比较的还是对应的堆元素。因为中间有了这么一道转换，看起来稍微有点困难。我们可以这样来理解。假设我们要构成前面示例中的最小堆，它的二叉树结构里应该保存的样式是上图那样的。但是，因为我们考虑到具体的参加比较的堆元素如果变动位置的话比较麻烦，就让它们的位置不动。也就是说，前面的线性结构元素应该是上图那样的，但是因为我们这里不让堆元素动，所以它可能本身存的是如下的这样一个数组结构：

    但是因为我们需要构成一个最小堆，所以我们这里只能通过一个间接指向这些元素的一个引用数组来调整了。这就是我们所说的int[] pq这个数组。比如说以这个元素数组为例，对应的int[] pq数组则应该如下（假定我们对应的数组下标是从1开始）：

 

    显示成一个线性数组的样式则如下：

     通过这样的映射关系，当我们要取堆最小的元素，则首先取得pq[1]，这是对应的最小的堆元素所在下标，然后再从堆元素所在的数组key[]里取。对应的是key[pq[1]]。通过我们建立的这个数组pq，我们可以很容易的根据堆形式的结构来找到具体堆的元素。

    另外，因为我们堆会经常调整，比如有时候我们需要更新堆元素的值，因为堆的元素发生了变化，它就需要和它的父节点或者子节点进行比较以及交换。这个时候，因为调整的是pq的值，但是当我们比如说key[3]发生了变化。那么我们首先需要的还是要找到它对应的堆索引数组里的元素位置。更直白的说就是，我们知道了key[3]发生了变化，但是我们需要找到是pq[]里的哪个元素指向key[3]。所以，为了方便的找到这个对应的关系元素，我们还需要另外一个关系映射表。int[] qp。它保留的关系正好和int[] pq的相反。它们之间应该满足这样的一个关系： qp[pq[i]] = pq[qp[i]] = i

比如以前面的图为例，我们对应的int[] qp则应该如下:

    该怎么来看这个表呢？我们应该从key[]所在的索引来看，比如说当前我在访问的元素是key[2]，那么当前的这个key索引2, 再通过qp[2]得到3, 就可以知道它实在对应的映射堆的位置pq[3]。

    其实，就是这两个看起来不起眼的映射在后面的实现里起到非常大的作用。有了这些描述，我们整个的堆数据结构可以定义如下：

public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int NMAX;        // maximum number of elements on PQ
    private int N;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i

    /**
     * Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
     * @param NMAX the keys on the priority queue are index from 0 to NMAX-1
     * @throws java.lang.IllegalArgumentException if NMAX < 0
     */
    public IndexMinPQ(int NMAX) {
        if (NMAX < 0) throw new IllegalArgumentException();
        this.NMAX = NMAX;
        keys = (Key[]) new Comparable[NMAX + 1];    // make this of length NMAX
        pq   = new int[NMAX + 1];
        qp   = new int[NMAX + 1];                   // make this of length NMAX
        for (int i = 0; i <= NMAX; i++) qp[i] = -1;
    }
}

    从代码里面可以看到我们故意多申请一个元素，然后将访问的最小元素设定为下标1。这样在一些求节点的父节点和子节点的时候会稍微简化一些。初始化的时候，一个有意思的地方就是我们将qp里面所有元素都设置成-1。这在后面的一些结构调整方法里有奇效。

 

结构调整

    我们知道，堆里面元素的调整是构建这个堆最基础的条件，在一般的情况下可能包含有向下交换和向上交换。比如说在我们目前的最小堆情况下，当我们新增加一个元素进来的时候，我们可能要进行向上交换。而如果我们将顶点的元素移除并替换成其他节点的时候，就需要向下交换。我们一个个的讨论过来。

    首先，在原来默认堆排序的实现里，如果我们要交换两个节点，只要节点元素换一下就可以了，因为这里基本的元素Key[]不动，那么要交换和调整的就是变动int[] pq和int[] qp了。它的实现如下：

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

    其中对qp[]的更新利用pq[qp[i]] == i这样的特性，可以很简单的实现。

     那么，对于向下交换的过程，则可以实现如下：

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

    因为以1开始作为下标，每个元素乘以2则表示它的左子节点。这里只要和它的节点比较就可以了。因为我们前面定义的Key是实现Comparable，所以这里greater方法就是Key的比较：

private boolean greater(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }

 

    同理，我们也可以得到向上调整的方法实现：

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

    结合前面对堆排序等描述的文章，这些方面的理解基本无压力。所以这部分实现的要点就是要每次都注意好更新pq和qp。

    现在，我们再来看看对改进堆的一些操作实现。

 

增

    我们这里要实现的是对Key[]里面的索引i位置插入元素。因为这个结构可以支持动态对元素的调整。所以要注意检查这个原来的位置是不是已经被占用了。这里的判断是用contains(i)这个方法。

 

public void insert(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        N++;
        qp[i] = N;
        pq[N] = i;
        keys[i] = key;
        swim(N);
    }

     代码里我们因为要新加入一个元素到堆中，对应的堆结构映射其实是相当于添加到堆最后的那个元素然后在来向上调整。这也就是为什么我们这里设置的N用来表示当前堆里元素的个数，它在这里起到了设置调整以及映射关系的作用。

 

    contains()的方法实现如下：

public boolean contains(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        return qp[i] != -1;
    }

    它的时间复杂度为常数。因为我们开始设置的qp里都是-1的，除非已经设置了别的值了。所以这对于用来查询该索引是否被占用的效率非常高。当然，结合我们这里的问题，我们也可以直接通过堆元素所在的数组来判断，比如keys[i] == null之类的。

 

删

    删除元素这里主要的是删除最小元素，也包含删除某个特定的元素。我们先看删除最小的元素。我们都知道，在最小堆里，删除最小的元素就是去掉映射堆里索引为1的那个元素。然后再用最后的元素来替换它，接着进行向下调整。具体的实现如下：

 

public int delMin() { 
        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = pq[1];        
        exch(1, N--); 
        sink(1);
        qp[min] = -1;            // delete
        keys[pq[N+1]] = null;    // to help with garbage collection
        pq[N+1] = -1;            // not needed
        return min; 
    }

   我们要注意到的细节就是当真的删除这个元素时，对应的keys[]数组以及pq, qp数组的元素调整。keys里面将对应元素设置成null是为了防止内存泄漏的隐患。另外，特别注意到我们这里的delMin返回的是这个min所对应的Key的索引。这在多路归并里就很有用了。这就好比我删除这个最小元素的时候，就知道它所在的流位置。

 

    除了前面的删除最小元素，我们还有一个就是支持删除指定索引的元素，它的实现如下：

public void delete(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, N--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

   因为这里要将中间的某个元素给去掉，我们用最后面的元素替换这个元素，然后要同时进行向上交换和向下交换。向下交换我们可以理解，不过向上交换也是必须的。在某些情况下，这个堆最后面的元素可能比另外一个子树的父节点小。

 

查

    对元素的查找除了前面的contains()方法以外，还有查找最小元素的索引，最小元素的key值，给定某个索引的key值，它们的实现相对不是很复杂。一一列举如下：

public int minIndex() { 
        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];        
    }

 

public Key minKey() { 
        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];        
    }

 

public Key keyOf(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }

   因为实现很简单，也很容易明白，这里就不再详细的解释了。

 

改

    对一些元素值的更新包括有增加key值，减少key值或者就是简单的修改key值。它们的实现如下：

public void increaseKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
        sink(qp[i]);
    }

    因为是增加key的值，所以我们只需要考虑向下交换就可以了。这里通过qp[i]将对应的qp[]索引返回进行交换就可以了。

 

   相应的，减少key值，则需要向上交换，对应的实现如下：

public void decreaseKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
        swim(qp[i]);
    }

    这里唯一稍微有点不同的就是修改key值，因为我们不知道这个key值是增加了还是减少了，所以需要同时在上下两个方向进行交换：

public void changeKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

 

    除了上述的基本操作，还有一些方法比如判断堆是否空，取得堆长度之类的方法，因为比较简单，这里也就不再赘述了。

 

K路归并的实现

   在前面一些讨论多路归并的文章里，我一再提到过，这个问题的关键就在于当我们找到某个最小元素的时候，需要找到它同时所对应的堆。在IndexMinPQ里的delMin恰好就解决了这个问题。所以在下面的实现里，利用这个我们可以不断的将对应的元素加入到堆中间进行调整。

 

private 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()); 

        // Extract and print min and read next from its stream. 
        while (!pq.isEmpty()) {
            StdOut.print(pq.minKey() + " "); 
            int i = pq.delMin(); 
            if (!streams[i].isEmpty()) 
                pq.insert(i, streams[i].readString()); 
        }
    } 

    从代码中我们还可以看到，我们需要判断一下，每次删除这个元素的时候，判断一下这个流还有没有空，如果没有空的话，还要读入新的元素加入到堆里。这里是以String类型作为示例。详细的实现可以参照后面的参考材料。

 

总结

    关于堆的一些变体在一些具体的应用，比如多路归并的实现，图算法的实现里都有一定的应用。只是它们的应用和一些特性的需求采用传统的堆功能并不能满足所有需求，所以才在这里引入了IndexMinPQ等实现。和传统的实现比起来，它支持对堆里的元素按照索引的方式来修改，好像我们访问一个数组一样，同时它的访问时间复杂度很低，一般是常熟或者logN级别。当然，这里良好性能的保障在于我们付出了额外两个数组来保存元素和堆索引之间的映射。可以说是一种典型的空间换时间思路。里面的很多细节值得细细推敲。

 

参考材料

http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

http://algs4.cs.princeton.edu/24pq/Multiway.java.html