每周学点大数据 | No.32优先队列

No.32期

优先队列

Mr. 王：我们回到这个问题中，如果是在内存中，我们只需要对前面的这些点做一个拓扑排序，就可以保证每一个节点在求解时，它们的所有入度节点都已经求出来了。

我们现在要考虑的就是，这种方法在磁盘中如何去实现。首先，我们要先将所有节点的拓扑序列求出来，如图中的蓝色标号，就是其拓扑序列。这里采用的就是前面说到的时间前向处理方法。我们借助一个数据结构，叫作优先队列。

小可：队列是满足先进先出策略的一个线性结构，那优先队列是什么？

Mr. 王：优先队列满足这样一个条件 ：优先队列中每个节点都有一个值，以任意顺序入优先队列的节点，会以值从小到大的顺序出队列。

优先队列的内部是一个堆，今天我们先不谈其内部实现，你只要知道优先队列的出队列顺序，与其值的大小有关，值小的先出队列，值大的后出队列，而不是入队列时的顺序就可以了。

Mr. 王：在这里我们使用的优先队列中的节点不是顶点，而是边。每条边的记法为（终节点的拓扑编号 , 始节点的拓扑编号 , 始节点上的布尔变量）这样的一个三元组，比如 1 号节点到 6 号节点这条边记作（6,1,0）。

而在优先队列中，我们用来做比较的值是终节点的拓扑编号这个数据域。也就是说，被压入优先队列的节点的拓扑编号越小，在出队列时就会先取出它。

小可：那么算法具体是怎么运行的呢？

Mr. 王：还是用刚才的例子。

第1 步：我们将(6,1,0) 这个数据记录压入优先队列中。有关1 号节点所有的边，我们都已经处理完毕了。

第2 步：我们处理2 号节点，方法是同样的。注意，2 号节点有两条边，这两条边都要处理。，注意优先队列中的点，它们会按照第一个数据域“终节点的拓扑编号”进行排序，以便最后按照从小到大的顺序出队列。虽然(6,1,0) 是先入队列的，但是4 的值比它们小，所以(4,2,1)要排在前面。

相应地，3 号节点也处理完毕。此时，所有的没有入度的这些初始节点都已经被处理完毕。下面我们沿着优先队列进行处理。从优先队列中弹出值最小的两条边，并且进行处理，本例中是4 号节点的两个入度边，源点分别为2 和3，值为1 和0，计算可得4 的值是0。

求出4 的值是0 之后，它的两条出度边也就应该被压入优先队列中。由于7 和8 这两个值是最大的，所以它们出现在优先队列的后面。

接下来，该算法用同样的方法进行计算，直至优先队列被最终清空时，算法停止。此时，所有节点上的值都已经有了结果。

小可笑着说：又到了分析复杂度的时候了。

Mr. 王：假设在算法开始前已经有了拓扑序列，剩下的算法可以划分为两部分，其中一部分是扫描所有的点和边，这里面的复杂度是 O(scan(|V| + |E|))；另一部分是维护优先队列的开销。由于这个数据量非常大，我们不得不把优先队列放在外存中。

统计一下，每条边都要从优先队列中进出一次，总共执行 O(|E|) 个优先队列操作，而优先队列的时间复杂度与对其排序的下界是一致的，所以这部分的 I/O 复杂度为O(sort(|E|))。综合起来，有一个定理：一个DAG G = (V,E)可以用 O(sort(|V|+ |E|)) 次 I/O 计算。

小可：嗯，有了这个方法之后，我们如何去求解最大独立集呢？

内容来源：灯塔大数据