优先级队列

• 下载源代码文件 - 1.59 Kb
• 下载演示项目 - 5.31 Kb

引言

许多算法 - 例如 Dijkstra 著名的最短路径搜索 - 在使用“半排序”列表时效率最高，该列表始终将最小元素放在最前面。为此目的最有效的结构是堆，也称为优先级队列。

用法

PriorityQueue 类是在 System.Collections 命名空间的指导方针下构建的。比较是通过 IComparer 接口完成的，或者，如果没有指定，则通过提供的对象的 IComparable 实现完成。优先级队列中的对象不必具有完全相同的类型，但它们必须相互可比较。

除了标准的 System.Collections 方法（Count、Contains，等等）之外，优先级队列还支持 3 个主要操作

• Push()：这将向优先级队列添加一个对象，并重新调整结构，以便如果该元素是当前最小的元素，则将其放在最前面。该操作的复杂度为 O(ld n)。
• Pop()：这将删除并返回优先级队列的当前头部，该头部始终是最小元素。复杂度为 O(ld n)。
• Update()：可能需要更改已在队列中的元素。由于这不太常见（您需要先找到该元素），因此只能通过显式的 IList 实现来完成（不应在任何其他情况下使用索引器）。设置索引器后，优先级队列将自动重新排序。复杂度为 O(ld n)（意料之中；））

示例

/// We create a PQ, add some random numbers and retreive them in sorted order:

IPriorityQueue PQ = new BinaryPriorityQueue();
Random R = new Random();
int i;
for(i=0;i<50;i++)
{
    PQ.Push(R.Next(1000));
}
while(PQ.Count>0)
    Console.WriteLine(PQ.Pop());

历史

• 2004 年 3 月 30 日 - 插入。
• 2004 年 3 月 31 日 - 将主类重命名为 BinaryPriorityQueue。

  创建了 IPriorityQueue 接口。