C# 中的优先队列

• 下载源文件 - 4.56 Kb

引言

最近，我正在创建一个状态机，其中需要带有时间戳的事件。我需要的不仅仅是简单的时钟滴答声，而是带有自己 ID 的定时事件，以便我可以区分不同的事件。研究这个问题让我想到使用优先级队列。我可以将带有时间戳的事件及其信息以任何顺序排入队列；优先级队列将负责正确地排列事件。计时器会定期检查优先级队列，看队列头部的事件是否到了触发时间。如果是，它会将事件出队并调用与之关联的委托。这种方法正是我所寻找的。

在 CodeProject 上搜索，我发现一个优先级队列[^]类已经写好了。但是，我想到可以很容易地用我的老朋友跳跃列表来编写自己的优先级队列。这样做的好处是出队操作只需要 O(1) 的时间，而入队操作平均仍然是 log(n)。我认为以这种方式使用跳跃列表足够新颖，值得专门写一篇文章。所以这就是它。我希望你觉得它有趣。

将跳跃列表用作优先级队列

关于跳跃列表的描述，我将引导您阅读我的跳跃列表[^]文章。本文中，我将重点介绍如何使用它们来实现优先级队列以及我的PriorityQueue类。

下面是优先级队列在出队操作之前的跳跃列表的插图。由于跳跃列表是由一系列节点一个接一个连接而成，因此从列表前面移除项只是移除第一个节点的问题。

箭头指向列表中的第一个项目。请注意，它指向标题后的第一个节点。标题节点始终存在于跳跃列表中，无论列表中是否有其他节点，并且实际上不包含项目；它用于标记列表的开头，并用作遍历列表的起点。

另请注意，这些项目按降序排列。由于这是一个优先级队列，因此项目从大到小排列。但是，有时您可能希望项目按升序排列，即较低的值具有比较高的值更高的优先级。我稍后将讨论如何使用我的 PriorityQueue 类实现这一点。但我有点超前了。

接下来，我们看到列表的前一个头部已被移除，列表中原本是第二个的项现在已成为列表中的第一个项。由于移除第一个节点（标题之后）不影响其后的节点，因此无需重新平衡。我们确实必须更新标题，使其指针（直到被移除节点的级别）现在指向其后的节点。这花费的时间很少。

PriorityQueue 类

当我决定使用跳跃列表来实现优先级队列时，我首先想到的是重用我的SkipList[^]类。然而，我希望优化出队操作，所以我决定为我的新PriorityQueue类从头开始重写算法。幸运的是，跳跃列表算法非常简单，可以快速轻松地完成。

PriorityQueue 类实现了 System.Collections 命名空间中的 ICollection 接口。此外，它还具有以下方法：

• Enqueue - 将元素添加到 PriorityQueue 中。
• Dequeue - 从 PriorityQueue 的头部移除元素。
• Remove - 从 PriorityQueue 中移除指定元素。
• Contains - 返回一个值，指示 PriorityQueue 中是否包含指定元素。
• Peek - 返回 PriorityQueue 中的第一个元素，而不将其移除。
• Clear - 从 PriorityQueue 中移除所有元素。

这些方法几乎都是跳跃列表算法的直接实现。Dequeue 算法是使跳跃列表作为优先级队列特别有用的原因，所以我将讨论它的实现方式。

public virtual object Dequeue()
{
    #region Require

    if(Count == 0)
    {
        throw new InvalidOperationException(
            "Cannot dequeue into an empty PriorityQueue.");
    }

    #endregion

    // Get the first item in the queue.
    object element = header[0].Element;

    // Keep track of the node that is about to be removed.
    Node oldNode = header[0];

    // Update the header so that its pointers that pointed to the
    // node to be removed now point to the node that comes after it.
    for(int i = 0; i < currentLevel && header[i] == oldNode; i++)
    {
        header[i] = oldNode[i];
    }

    // Update the current level of the list in case the node that
    // was removed had the highest level.
    while(currentLevel > 1 && header[currentLevel - 1] == null)
    {
        currentLevel--;
    }

    // Keep track of how many items are in the queue.
    count--;

    version++;

    #region Ensure

    Debug.Assert(count >= 0);

    #endregion

    #region Invariant

    AssertValid();

    #endregion

    return element;
}

从上到下

• 测试前置条件。我将其放在自己的区域中，以将其与代码的其余部分区分开来。我将该区域命名为“Require”，以向 Eiffel 编程语言致敬。出队操作的前置条件是优先级队列不能为空。如果尝试对空优先级队列执行出队操作，则会抛出异常。
• 获取列表中的第一个元素。此列表中的节点由私有 Node 类表示。该类实现了一个索引器，可让您访问其“forward”指针或对列表中下一个节点的引用。要获取第一个元素，我们访问头部在最低级别（零）指向的节点。此元素将在出队操作结束时返回。
• 跟踪即将被移除的节点。我们需要这样做，以便可以更新接下来要进行的头部。
• 更新头节点，使其原来指向被移除节点的指针现在指向其后的节点。
• 更新列表的当前级别。有可能被移除的节点在列表中具有最高级别。如果是这样，我们需要更新列表级别。
• 更新列表计数。
• 更新 PriorityQueue 版本。当创建 PriorityQueue 枚举器时，它会存储 PriorityQueue 的版本。当执行操作（例如 MoveNext）时，枚举器将比较其存储的版本与当前 PriorityQueue 版本，以确保 PriorityQueue 未更改。理论上，如果版本值在枚举器检查之前全部回滚，这可能会导致问题。然而，这似乎极不可能。
• 下一个区域是“Ensure”区域。它检查后置条件。在这里，我只检查以确保计数是非负数。更健壮的实现可能会存储旧的计数值，并确保新的计数值是旧计数值减一。但这对我来说在这里似乎是多余的。
• 接下来是“Invariant”区域。它调用了一个 AssertValid 方法。此方法仅在调试版本中编译。它测试以确保 PriorityQueue 的任何不变量都未被违反。
• 最后，返回位于 PriorityQueue 头部的元素。

PriorityQueue 类提供了两个构造函数，一个默认构造函数，以及一个接受 IComparer 对象的构造函数。如果使用默认构造函数，PriorityQueue 将其元素转换为 IComparable 接口，以便比较它们以确定它们在列表中的优先级和顺序。当然，这假设如果使用默认构造函数，则排入 PriorityQueue 的元素实现了 IComparable 接口。否则，在尝试比较元素时将抛出异常。如果使用 IComparer 构造函数，PriorityQueue 将使用指定的 IComparer 对象进行元素比较。

PriorityQueue 以降序排列元素。这意味着如果使用 IComparable 或 IComparer 进行比较的结果大于零，它将把该元素排在与之比较的元素之前。如果您需要按升序排列元素，您的 IComparable 或 IComparer 对象需要在某个元素小于与之比较的元素时返回大于零的值，而在某个元素大于与之比较的元素时返回小于零的值。此外，允许重复。如果两个元素相等，则将排入 PriorityQueue 的元素插入到队列中已有的元素之前。

结论

这次经历让我对跳跃列表数据结构重新燃起了敬意。它确实非常精巧。我希望您觉得这个类有用，一如既往，欢迎您的评论和建议。谢谢！

历史

• 2006 年 3 月 3 日 - 第一版发布。
• 2006 年 3 月 11 日 - 修复了 Contains 方法中的错误。