C#中的优先队列实现

Question

我正在尝试使用SortedDictionary实现优先级队列机制，并希望得到关于我的当前实现的建议。

我的实现如下：

public class PriorityQueue
{
    private Object lockObj;
    private SortedDictionary<PQMsgPriority, Queue<PQMessage>> messageDictionary; 

    public PriorityQueue()
    {
        lockObj = new object();
        messageDictionary = new SortedDictionary<PQMsgPriority, Queue<PQMessage>>();
    }

    public void Enqueue(PQMessage item)
    {
        lock (lockObj)
        {
            if(item != null && item.MsgPriority == PQMsgPriority.None)
            {
                if (messageDictionary.ContainsKey(item.MsgPriority))
                {
                    Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
                    dataList.Enqueue(item);
                    messageDictionary[item.MsgPriority] = dataList;
                }
                else
                {
                    Queue<PQMessage> dataList = new Queue<PQMessage>();
                    dataList.Enqueue(item);
                    messageDictionary.Add(item.MsgPriority, dataList);
                }
            }
        }
    }

    public PQMessage Dequeue()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;
            PQMsgPriority deleteKey = PQMsgPriority.None;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Dequeue();
                messageDictionary[item.Key] = dataList;

                //If there is no more elements remaining in the list, set a flag (deleteKey) for deleting the key
                if (dataList.Count == 0) 
                    deleteKey = item.Key;

                break;
            }

            //If the deleteKey flag is set, delete the key from the dictionary
            if (deleteKey != PQMsgPriority.None)
                messageDictionary.Remove(deleteKey);

            return messageData;
        }
    }

    public int Count()
    {
        lock (lockObj)
        {
            return messageDictionary.Count;
        }
    }

    public PQMessage Peek()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Peek();
                break;
            }

            return messageData;
        }
    }
}

public enum PQMsgPriority
{
    High = 0,
    Medium = 1,
    Low = 2,
    None = 3
}

public class PQMessage
{
    private PQMsgPriority msgPriority;
    private Object message;

    #region Properties
    public PQMsgPriority MsgPriority
    {
        get { return msgPriority; }
        set { msgPriority = value; }
    }
    public Object Message
    {
        get { return message; }
        set { message = value; }
    }
    #endregion

    public PQMessage(PQMsgPriority msgPriority, Object message)
    {
        this.msgPriority = msgPriority;
        this.message = message;
    }
}

如果有其他实现优先队列的方法，请指点我正确的方向。

- Anil Mathew

---

http://codereview.stackexchange.com/ - L.B

我不明白为什么你在Enqueue中使用item.MsgPriority == PQMsgPriority.None？这是为了什么？ - Roman Golenok

好问题。如果设置了某些标志，就不需要将某些消息添加到队列中，因此需要添加检查以处理这些消息。 - Anil Mathew

有没有完整的源代码的最终解决方案？ - Kiquenet

https://codereview.stackexchange.com/questions/11836/priority-queue-implementation-in-c - Anil Mathew

Answer 1

我应该在这里声明，我假设你是为了学习而不是实现一个强壮的解决方案。如果你想要一个只是运行的东西，那么最好重用现有的实现。

下面是一些一般性的评论。在下面的示例中，第三行是不必要的。

Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
dataList.Enqueue(item);
messageDictionary[item.MsgPriority] = dataList;

从messageDictionary返回的dataList是映射中引用的副本。这意味着当你将数据Enqueue时，它仍在使用之前的底层队列（而不是队列的副本），因此无需再次放回，只需删除该行即可。

在你的出列实现中，你有一个循环，在每次循环时都会在第一个元素上中断(例如，你只会走一遍循环)。也许你可以考虑使用LINQ来获取First元素并立即返回它?(类似于Peek实现)。

最后，鉴于PQMessage本身具有优先级，也许你可以考虑为你的实现使用SortedList?(请参阅这里)

- Jeff Foster

Answer 2

如果您需要提高并发性能，可以只锁定一个队列进行写操作。（仍需要对整个SortedDictionary进行读锁定）。

而且不要忘记按正确顺序设置和释放锁。

- gabba