ALDS1_9_C: Priority Queue

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q032 優先度付きキュー https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        if (InputPattern == "Input1") {
            WillReturn.Add("insert 8");
            WillReturn.Add("insert 2");
            WillReturn.Add("extract");
            WillReturn.Add("insert 10");
            WillReturn.Add("extract");
            WillReturn.Add("insert 11");
            WillReturn.Add("extract");
            WillReturn.Add("extract");
            WillReturn.Add("end");
            //8
            //10
            //11
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static Dictionary<int, int> mHeapDict = new Dictionary<int, int>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList) {
            string[] SplitArr = EachStr.Split(' ');

            if (SplitArr[0] == "insert") {
                HeapIncreaseKey(int.Parse(SplitArr[1]));
            }
            if (SplitArr[0] == "extract") {
                sb.Append(Extract());
                sb.AppendLine();
            }
        }
        Console.Write(sb.ToString());
    }

    // Insert処理
    static void HeapIncreaseKey(int pAddValue)
    {
        int CurrNode = 1 + mHeapDict.Count;
        mHeapDict[CurrNode] = pAddValue;

        while (1 < CurrNode && mHeapDict[CurrNode / 2] < mHeapDict[CurrNode]) {
            int Swap = mHeapDict[CurrNode];
            mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
            mHeapDict[CurrNode / 2] = Swap;

            CurrNode /= 2;
        }
    }

    // Extract処理
    static int Extract()
    {
        int MaxVakue = mHeapDict[1];
        int LastNode = mHeapDict.Count;
        mHeapDict[1] = mHeapDict[LastNode];
        mHeapDict.Remove(LastNode);

        MaxHeapify(1);
        return MaxVakue;
    }

    // 根ノードを指定し、根から葉へヒープ構築
    static void MaxHeapify(int pRootNode)
    {
        if (mHeapDict.Count <= 1) {
            return;
        }

        int Left = pRootNode * 2;
        int Right = pRootNode * 2 + 1;

        // 左の子、自分、右の子で値が最大のノードを選ぶ
        int Largest = mHeapDict[pRootNode];
        int LargestNode = pRootNode;

        if (mHeapDict.ContainsKey(Left) && mHeapDict[Left] > Largest) {
            Largest = mHeapDict[Left];
            LargestNode = Left;
        }
        if (mHeapDict.ContainsKey(Right) && mHeapDict[Right] > Largest) {
            Largest = mHeapDict[Right];
            LargestNode = Right;
        }

        // 子ノードのほうが大きい場合
        if (LargestNode != pRootNode) {
            int Swap = mHeapDict[LargestNode];
            mHeapDict[LargestNode] = mHeapDict[pRootNode];
            mHeapDict[pRootNode] = Swap;

            // 再帰的に呼び出し
            MaxHeapify(LargestNode);
        }
    }
}

解説

Dictionaryでヒープのノードを管理してます。