数据结构与算法系列（4）优先队列

数据结构与算法系列（4）优先队列2014-04-26 cnblogs 追忆前言

在生活中我们常常会遇到栈和队列的问题，比如放盘子、取盘子（类似栈）先进后出的集合，排队（类似队列）先进先出的集合。这两种情况在.NET里面已经有相关的类库Stack和Queue，在这里不再进行讨论，有兴趣的朋友可以百度一下这方面的资料。在这里主要讨论下优先队列，是在Queue基础上的扩展。

1.优先队列

大家所知，队列是一种先进先出的数据结构。这种行为的效果就是会最先移除结构内最早进入的数据项。然而，对于很多应用程序而言，需要一种可以把具有最高优先级的数据项最先移除的数据结构，即使这个数据项在结构中不是“最早进入的”一个。对于这类应用程序Queue有一种特殊的情况，那就是优先队列。

许多应用程序在操作中都用到了优先队列。一个很好的实例就是在计算机操作系统内的进程处理。某些进程可能有高于其他进程的优先级，比如打印机进程就有典型的低优先级。进程（或任务）通常会根据优先级进行编号，Priority（优先级）为0的进程比Priority为20的任务具有更高的优先级。

通常会把存储在优先队列中的数据项作为键值对来构造，其中关键字就是指优先级别，而值则用来识别数据项。例如，可以按照如下形式对一个操作系统进程进行定义：

struct Process

{

int priority;

string name;

}

我们不能把未修改的Queue对象用于优先队列。DeQueue方法在被调用时只会把队列中的第一个数据项移除。但是，大家可以从Queue类派生出自己的优先队列类，同时覆盖DeQueue方法来实现自己的需求。

我们把这个类称为PQueue。所有Queue的方法都可以照常使用，同时覆盖DeQueue方法来移除具有最高优先级的数据项。为了不从队列前端移除数据项，首先需要把队列的数据项写入一个数组。然后遍历整个数组从而找到具有最高优先级的数据项。最后，根据标记的数据项，就可以不考虑此标记数据项的同时对队列进行重建。

具体类的代码如下：

public struct PQItem

{

public int Priority;

public string Name;

}

public class PQueue : Queue

{

public PQueue（）

{

}

public override object Dequeue（）

{

object[] items;

int min;

items = this.ToArray（）;

min = （（PQItem）items[0]）.Priority;

for （int x = 1; x <= items.GetUpperBound （0）; x++）

{

if （（（PQItem）items[x]）.Priority < min）

{

min = （（PQItem） items[x]）.Priority;

}

this.Clear（）;

int tmp;

for （tmp = 0; tmp <= items.GetUpperBound （0）; tmp++）

{

if （（（PQItem）items [tmp]）.Priority == min &&

（（PQItem）items [tmp]）.Name ！= ""）

this.Enqueue （items[tmp]）;

}

return base.Dequeue（）;

}