优先队列的应用

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

优先队列常用于解决两种问题：

选择问题

选择问题需要解决的问题大致可以描述为：从输入的 N 个元素中，找到第 k 个最大的元素。

算法一：第一个能够想到的解决办法是简单排序算法，这个算法的运行时间为 $O(N^2)$ .

算法二：这个算法是在简单排序的算法上做了改进：首先将 k 个元素读入一个数组并将其排序，此时，第 k 个位置上的元素就是最小的元素，一个一个地处理其余的元素，使其与数组中的第 k 个元素比较，如果该元素大，那么将第 k 个元素除去，而这个新元素则被放在数组中其余 k-1 个元素间正确的位置上。当算法结束时，第 k 个位置上的元素就是问题的解。该算法的运行时间为 $O(N*k)$ 。

算法三：为了简单起见，假设我们只考虑找出第 k 个最小的元素。该算法很简单。我们将 N 个元素读入一个数组。然后对该数组应用 BuildHeap 算法。最后，执行 k 次 DeleteMin 操作。从该堆最后提取的元素就是我们的答案。显然，通过改变堆序性质，我们就可以求解原始的问题 —— 找出第 k 个最大的元素。这个算法的正确性应该是显然的。如果使用 BuildHeap，构造堆的最坏情形用时是 $O(N)$ ，而每次 DeleteMin 用时 $O(log N)$ 。由于有 k 次 DeleteMin，因此我们得到总的运行时间为 $O(N+klog\space N)$ 。如果 $k = O(\frac{N}{log N})$ ，那么运行时间取决于 BuildHeap 操作，即 $O(N)$ 。对于大的 k 值，运行时间为 $O(k \log N)$ 。如果 $k = \frac{N}{2}$ ，那么运行时间为 $O(N\log N)$ 。注意⚠️，如果我们对 $k= N$ 运行该程序并在元素离开堆时记录它们的值，那么我们实际上已经对输入文件以时间 $O(N \log N)$ 做了排序，这种快速的排序算法叫作堆排序（heapsort）。

算法四：我们回到原始问题，找出第 k 个最大的元素。这个算法的思路和算法二类似。在任意时刻我们都将维持 k 个最大元素的集合 S。在前 k 个元素读入之后，当再读入一个新的元素时，该元素将与第 k 个元素进行比较，记这第 k 个最大的元素为 $S_k$ 。注意， $S_k$ 是 S 中最小的元素。如果新的元素更大，那么用新的元素代替 S 中的 $S_k$ 。此时，S 将有一个新的最小元素，它可能是新添加的元素，也可能不是。在输入终了时，我们找到 S 中最小的元素，将其返回，它就是答案。与算法二不同的是，这里我们使用一个堆来实现 S。前 k 个元素通过调用一次 BuildHeap 以总时间 $O(k)$ 被置入堆中。处理每个其余的元素的时间为 $O(1)$ （检验元素是否进入 S）再加上时间 $O(\log k)$ （在必要时删除 $S_k$ 并插入新元素）。因此，总的时间是 $O(k+(N-k)\log k) = O(N \log k)$ 。该算法也给出找出中位数的时间界 $O(N \log N)$ 。

事件模拟

对于某些概率分布以及 k 的一些值，答案都可以精确地计算出来。然而随着 k 变大，分析明显变得困难，因此使用计算机模拟事件的运作很有吸引力。比如，可以用这种方法，银行官员可以确定为保证合理，通畅的服务需要多少出纳员。

模拟由处理中的事件组成。我们以银行系统为例，这里的两个事件是：一位顾客的到达，以及一位顾客的离去从而腾出一名出纳员。

我们可以使用概率函数来生成一个输入流，它由每位顾客的到达时间和服务时间的序偶组成，并通过到达时间排序。我们不必使用一天中的准确时间，而是使用单位时间量，称之为一个滴答（tick）。

进行这种模拟的一个方法是启动在 0 滴答处的一台模拟钟表。我们让钟表一次走一个滴答，同时查看是否有一个事件发生。如果有，那么我们处理这个（些）事件，搜索统计资料。当没有顾客留在输入流中且所有的出纳员都闲着的时候，模拟结束。

这种模拟策略的问题是，它的运行时间不依赖顾客数或事件数（每位顾客有两个事件），但是却依赖滴答数，而后者实际又不是输入的一部分。为了看清为什么问题在于此，假设将钟表的单位改成滴答的千分之一（millitick）并将输入中的所有时间乘以 1000，则结果将是模拟用时长了 1000 倍！

避免这种问题的关键是在每一个阶段让钟表直接走到下一个事件的事件。从概念上看这是容易做到的。在任意时刻，可能出现的下一个事件或者是输入文件中下一个顾客的到达，或者是在一名出纳员处一位顾客离开。由于可以得知将发生事件的所有时间，因此我们只需找出最近的要发生的事件并处理这个事件。

如果事件是离开，那么处理过程包括搜集离开的顾客的统计资料以及检验队伍（队列）看是否还有另外的顾客在等待。如果有，那么我们加上这位顾客，处理所需要的统计资料，计算该顾客将要离开的时间，并将离开事件加到等待发生的事件集中。

如果事件是到达，那么我们检查闲着的出纳员。如果没有，那么我们把该到达事件放到（队伍）队列中；否则，我们分配顾客一个出纳员，计算顾客的离开时间，并将离开事件加到等待发生的事件集中。

在等待的顾客队伍可以实现为一个队列。由于我们需要找到最近的将要发生的事件，合适的办法是将等待发生的离开的集合编入一个优先队列中。下一个事件是下一个到达或下一个离开（那个发生早就是哪个），它们都容易达到。

为模拟编写例程很简单，但是可能很耗费时间。如果有 C 个顾客（因此有 2C 个事件）和 k 个出纳员，那么模拟的运行时间将会是 $O(C \log(k+1))$ ，因为计算和处理每个事件花费 $O(\log H)$ ，其中 $H= k+1$ 为堆的大小。

优先队列的应用

选择问题

事件模拟

猜你喜欢

热点阅读