优先队列

2022-04-18 本文已影响0人 Sun东辉

在多用户环境中，操作系统调度程序必须决定在若干进程中运行哪个进程。一般只允许一个进程运行一个固定的时间片。一种算法是使用一个队列。开始时将作业放到队列的末尾。调度程序将反复提取队列中的第一个作业并运行它直到运行完毕，或者在该作业的时间片用完但未运行完毕时把它放到队列的末尾。这种策略一般并不太合适，因为一些很短的作业由于一味等待运行而要花费很长的时间去处理。一般说来，短的作业要尽快地结束，这一点很重要，因此在已运行过的作业当中这些短作业应该拥有优先权。此外，有些作业虽不短小但很重要，也应用拥有优先权。这种特殊的应用需要一类特殊的队列，我们称之为优先队列（priority queue）。

模型

优先队列是允许至少下列两种操作的数据结构：Insert（插入），它的工作是显而易见的；以及 DeleteMin（删除最小者），它的工作是找出、返回和删除优先队列中最小的元素。Insert 操作等价于 Enqueue（入队），而 DeleteMin 则是队列中 Dequeue（出队）在优先队列中的等价操作。DeleteMin 函数也变更它的输入。软件工程界当前的想法认为这不再是一个好的思路。不过，处于历史原因我们还是需要使用这个函数；许多程序设计人员期望 DeleteMin 以这种方式运行。

如果大多数数据结构那样，有时可能要添加一些操作，但这些添加的操作属于拓展的操作，不属于基本模型。

除了操作系统外，优先队列还有许多应用。比如，可以用于外部排序，在贪婪算法（greedy algorithm）的实现方面优先队列也很重要，该算法通过反复求出最小元来进行计算。

一些简单的实现

有几种明显的方法实现优先队列。

我们可以使用一个简单的链表在表头以 $O(1)$ 执行插入操作，并遍历该链表以删除最小元，这又需要 $O(N)$ 时间。
另一种方法是，始终让表保持排序状态；这使得插入代价高昂（ $O(N)$ ）而 DeleteMin 花费低廉（ $O(1)$ ）。基于 DeleteMin 的操作次数从不多于删除操作次数的事实，因此前者恐怕是更好的想法。
还有一种实现优先队列的方法是使用二叉查找树，它对这两种操作的平均运行时间都是 $O(\log N)$ 。尽管插入是随机的，而删除则不是，但是这个结论还是成立的。记住我们删除的唯一元素是最小元。反复除去左子树中的节点似乎损害树的平衡，使得右子树加重。然而，右子树是随机的。在最坏的情形（即 DeleteMin 将左子树删空的情况）下，右子树拥有的元素最多也就是它应具有的两倍。这只是在其期望的深度上加了一个小常数。注意，通过使用平衡树，可以把界变成最坏情形的界，这将防止出现坏的插入序列。

使用查找树可能有些过分，因为它支持许许多多并不需要的操作。大多数情况下，我们使用的基本的数据结构不需要指针，它以最坏情形时间 $O(\log N)$ 支持上述两种操作。插入实际上将花费常数平均时间，若无删除干扰，该结构的实现将以线性时间建立一个具有 N 项的优先队列。然后，如果实现优先队列以支持有效的合并，这个附加的操作似乎有些复杂，它显然需要使用指针。

二叉堆

有一种工具叫作二叉堆（binary heap），常用其实现优先队列，当不加修饰地使用堆（heap）这个词时一般都是指该数据结构的实现。这里，我们直接把二叉堆叫作堆。同二叉查找树一样，堆也有两个性质，即结构性和堆序性。正如 AVL 树一样，对堆的一次操作可能破坏这两个性质中的一个，因此，堆的操作必须要到堆的所有性质都被满足时才终止。事实上这并不难做到。

结构性质

堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树被称为完全二叉树（complete binary tree）。

很容易证明，一棵高为 $h$ 的完全二叉树有 $2^h$ 到 $2^{k+1}-1$ 个节点。这意味着，完全二叉树的高是 $\log N$ ，显然它是 $O(\log N)$ 的。

一项重要的观察发现，因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。

对于数组中任意位置 $i$ 上的元素，其左儿子在位置 $2i$ 上，右儿子在左儿子后的单元 $(2i+1)$ 中，它的父亲则在位置 $\frac{i}{2}$ 上，因此，不仅这里不需要指针，而且遍历该树所需要的操作也极其简单，在大部分计算机上运行得速度可能会非常快。这种实现方法的唯一问题在于，最大的堆大小需要事先估计，但对于典型的情况这并不成问题。

因此，一个堆数据结构将由一个数组（不管关键字是什么类型）、一个代表最大值的整数以及当前的堆大小组成。

堆序性质

使操作快速执行的性质是堆序（heap order）性。由于我们想要快速地找出最小元，因此最小元应该在根上。如果我们将任意子树也视为一个堆，那么任意节点就应该小于它的所有后裔。

应用这个逻辑，我们得到堆序性质。在一个堆中，对于每一个节点 X，X 的父亲中的关键字小于（或等于）X 中的关键字，根节点除外（它没有父亲）。

根据堆序性质，最小元总可以在根处找到。因此，我们以常数时间完成附加运算 FindMin。

基本的堆操作

无论从概念上还是实际上考虑，执行这两种所要求的操作都是容易的，只需要始终保持堆序性质。

Insert(插入)

为将一个元素 X 插入到堆中，我们在下一个空闲位置创建一个空穴，否则该堆将不是完全树。如果 X 可以放在该空穴中而并不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上行一步。继续该过程直到 X 能被放入空穴中为止。如图 6-6 所示，为了插入 14，我们在堆的下一个可用位置建立一个空穴。由于将 14 插入空穴破坏了堆序性质，因此将 31 移入该空穴。在图 6-7 中继续这种策略，直到找出置入 14 的正确位置。

这种一般的策略叫作上滤（percolate up）：新元素在堆中上滤直到找出正确的位置。

代码实现如下：

/* H->Element[0] is a sentinel */

void
Insert(ElementType X, PriorityQueue H)
{
    int i;

    if( IsFull(H))
    {
        Error(" Priority queue is full");
        return;
    }

    for( i = ++ H->Size; h->Elements[i/2]>X; i /= 2)
        H->Elements[i] = H->Elements[i/2];
    H->Elements[i] = X;
}

其实我们本可以使用 Insert 例程通过反复实施交换操作直至建立正确的序来实现上滤过程，可是一次交换需要三条赋值语句。如果一个元素上滤 $d$ 曾，那么由于交换而实施的赋值的次数就达到 $3d$ ，而这里的方法却只用 $d+1$ 次赋值。

如果要插入的元素是新的最小值，那么它将一直被推向顶端。这样在某一时刻， $i$ 将是 1，我们就要令程序跳出 while 循环。当然我们可以用明确的测试做到这一点，不过，我们采用的是把一个很小的值放到位置 0 处以使 while 循环得以终止。这个值必须保证小于（或等于）堆中的任何值，我们称之为标记（sentinel）。这种想法类似于链表中头节点的使用。通过添加一条哑信息（dummy piece of information），我们避免了每个循环都要执行一次测试，从而节省了一些时间。

如果欲插入的元素是新的最小元从而一直上滤到根处，那么这种插入的时间高达 $O(log N)$ 。平均看来，这种上滤终止得要早；已证明，执行一次插入平均需要 2.607 次比较，因此 Insert 将元素平均上移 1.607 层。

DeleteMin（删除最小元）

DeleteMin 以类似于插入的方式处理。找出最小元是容易的，困难的部分是删除它。当删除一个最小元时，在根节点处产生了一个空穴。由于现在堆少了一个元素，因此堆中最后一个元素 X 必须移动到该堆的某个地方。如果 X 可以放到空穴中，那么 DeleteMin 完成。不过这一般不太可能，因此我们将空穴的两个儿子中较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到 X 可以放入空穴。因此，我们的作法是将 X 置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。

在图 6-9 中左边的图显示 DeleteMin 之前的堆。删除 13 后，我们必须要正确地将 31 放到堆中。31 不能放在空穴中，因为这将破坏堆序性质。于是，我们把较小的儿子 14 置入空穴，同时空穴下滑一层（见图 6-10）。重复该过程，把 19 置入空穴，在更下一层上建立一个新的空穴。然后，再把 26 置入空穴，在底层又建立新的空穴。最后，我们得以将 31 置入空穴（见图 6-11）。这种一般的策略叫作下滤（percolate down）。在其实现例程中我们使用类似于 Insert 例程中用过的技巧来避免进行交换操作。

在堆的实现中经常发生的错误是当堆中存在偶数个元素的时候，此时将遇到一个节点只有一个儿子的情况。不要假设节点总有两个儿子，因此这就涉及一个附加的测试。一个极其巧妙的解决办法是始终保证你的算法把每一个节点都看成有两个儿子。为了实施这种解法，当堆的大小为偶数时，在每个下滤开始时，可将其值大于堆中的任何元素的标记放到堆的终端后面的位置上。你必须在深思熟虑以后再这么做，而且必须要判断你是否确实要使用这种技巧。虽然这不再需要测试右儿子的存在性，但是你还是需要测试何时到达底层，因为对每一片树叶算法将需要一个标记。

这种算法的最坏情形运行时间为 $O(\log N)$ 。平均而言，放在根处的元素几乎下滤到堆的底层（它所来自的那层），因此平均运行时间为 $O(\log N)$ 。

其他的堆操作

注意，虽然求最小值操作可以在常数时间完成，但是，按照求最小元设计的堆（也称作最小值（min）堆）在求最大元方面却无任何帮助。事实上，一个堆所蕴含的关于序的信息很少，因此，若不对整个堆进行线性搜索，是没有办法找出任何特定的关键字的。在很多大型堆结构中，半数的元素位于树叶上，此时，如果重要的是要知道元素都在什么地方，那么除堆之外，还必须用到诸如散列表等某些其他的数据结构。

如果我们假设通过某种其他方法得知每一个元素的位置，那么有几种其他操作的开销将变小。下述三种这样的操作均以对数最坏情形时间运行。

DecreaseKey（降低关键字的值）

$DecreaseKey(P,\triangle,H)$ 操作降低在位置 P 处的关键字的值，降值的幅度为正的量 $\triangle$ 。由于这可能破坏堆的序，因此必须通过上滤对堆进行调整。该操作对系统管理程序是有用的：系统管理程序能够使它们的程序以最高的优先级运行。

IncreaseKey（增加关键字的值）

$IncreaseKey(P,\triangle, H)$ 操作增加在位置 P 处关键字的值，增值的幅度为正的量 $\triangle$ 。这可以用下滤来完成。许多调度程序自动地降低正在过多地消耗 CPU 时间的进程的优先级。

Delete（删除）

$Delete(P,H)$ 操作删除堆中位置 P 上的节点。这通过首先执行 $DecreaseKey(P,\infty,H)$ ，再执行 $DecreaseMin(H)$ 来完成。当一个进程被用户终止（而不是正常终止）时，它必须从优先队列中除去。

BuildHeap（构建堆）

$BuildHeap(H)$ 操作把 N 个关键字作为输入并把它们放入空堆中。显然，这可以使用 N 个相继的 Insert（插入）来完成。由于每个 Insert 将花费 $O(1)$ 平均时间以及 $O(\log N)$ 的最坏情形时间，因此该算法的总运行时间则是 $O(N)$ 平均时间而不是 $O(N \log N)$ 最坏情形时间。由于这是一种特殊的指令，没有其他操作干扰，而且我们已经知道该指令能够以线性平均时间实施，因此，期望能够保证线性时间界的考虑是合乎情理的。

定理：包含 $2^{h+1}- 1$ 个节点、高为 $h$ 的理想二叉树（perfect binary tree）的节点的高度和为 $2^{h+1}-1-(h+1)$ 。