トップページに戻る    次の競技プログラミングのメモへ    前の競技プログラミングのメモへ

002 C#でC++のPriorityQueue

C#での、C++のPriorityQueueもどきです。

Enqueueは、定数オーダーですが
Dequeueは、Nかかります。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var PriorityQueue = new CppPriorityQueue();
        PriorityQueue.Enqueue(1, "優先度小");
        PriorityQueue.Enqueue(2, "優先度中");
        PriorityQueue.Enqueue(3, "優先度大");

        while (PriorityQueue.Count > 0) {
            PriorityQueueItemDef DeQueued = PriorityQueue.Dequeue();
            Console.WriteLine("Priority={0}。Memo={1}", DeQueued.Priority, DeQueued.Memo);
        }
    }
}

//PriorityQueueもどき
struct PriorityQueueItemDef
{
    internal int Priority;
    internal string Memo;
}
class CppPriorityQueue
{
    private List<PriorityQueueItemDef> mItemList = new List<PriorityQueueItemDef>();

    internal int Count { get { return mItemList.Count; } }

    internal void Enqueue(PriorityQueueItemDef pItem) { mItemList.Add(pItem); }

    internal void Enqueue(int pPriority, string pName)
    {
        mItemList.Add(new PriorityQueueItemDef() { Priority = pPriority, Memo = pName });
    }

    internal PriorityQueueItemDef Dequeue()
    {
        int wkInd = 0;
        for (int I = 1; I <= mItemList.Count - 1; I++) {
            if (mItemList[wkInd].Priority < mItemList[I].Priority)
                wkInd = I;
        }
        PriorityQueueItemDef WillRetun = mItemList[wkInd];
        mItemList.RemoveAt(wkInd);
        return WillRetun;
    }
}


実行結果

Priority=3。Memo=優先度大
Priority=2。Memo=優先度中
Priority=1。Memo=優先度小


解説

ダイクストラ法用に作ってみたクラスです。
ヒープ木で実装したほうが計算量が少ないと思いますが・・・