using System;
using System.Collections;

public class PriorityQueue : IEnumerable
{
    // Die an Push übergebenen Daten werden zusammen mit ihrer Priorität in Objekte der
    // Klasse Item verpack und so intern gespeichert
    public class Item
    {
        public Object obj;
        public int priority;

        public Item(Object obj, int priority)
        {
            this.obj = obj;
            this.priority = priority;
        }
    }

    // Intern werden die Daten in einem einfachen Array verwahrt
    private Item[] data;
    private int size;
    private const int blocksize = 10;

    public PriorityQueue()
    {
        data = new Item[blocksize];
        size = 0;
    }

    // Liefere das vorderste Datenelement zurück und lösche dieses gleichzeitig aus der 
    // Datenstruktur. Das das Löschen am effizientesten am Ende des Arrays ausgeführt 
    // werden kann, verwenden wir das hintere Ende des Arrays als vorderes Ende der 
    // PriorityQueue
    public Object Pop()
    {
        if (size == 0)
            return null;

        Object obj = data[--size].obj;
        data[size] = null;
        return obj;
    }

    // Datenelement einfügen
    public void Push(Object obj, int priority)
    {
        // internes Array bei Bedarf vergrößern
        if (size == data.Length)
        {
            Item[] newData = new Item[data.Length + blocksize];
            Array.Copy(data, 0, newData, 0, size);
            data = newData;
        }

        if (size == 0)
        {
            data[0] = new Item(obj, priority);
            ++size;
        }
        else
        {
            // Einfügeposition suchen
            int insertpos = size;

            while (insertpos > 0)
            {
                if (data[insertpos - 1].priority < priority)
                    break;

                --insertpos;
            }

            Array.Copy(data, insertpos, data, insertpos + 1, size - insertpos);
            data[insertpos] = new Item(obj, priority);
            ++size;
        }
    }

    // Enumerator zurückliefern
    public IEnumerator GetEnumerator()
    {
        return new PriorityQueueEnumerator(this);
    }

    // Enumerator-Klasse
    private class PriorityQueueEnumerator : IEnumerator
    {
        private Item[] data;
        private int current;

        internal PriorityQueueEnumerator(PriorityQueue pc)
        {
            data = new Item[pc.size];
            Array.Copy(pc.data, 0, data, 0, pc.size);
            current = data.Length;
        }

        public bool MoveNext()
        {
            --current;

            if (current < 0)
                return false;
            else
                return true;
        }

        public Object Current
        {
            get
            {
                if (current < 0)
                    throw new InvalidOperationException("Erst MoveNext() aufrufen");

                return data[current];
            }
        }

        public void Reset()
        {
            current = data.Length;
        }
    }

}

public class Program
{
    static void Main()
    {
        PriorityQueue pq = new PriorityQueue();

        pq.Push(10, 2);
        pq.Push(444, 3);
        pq.Push(123456, 6);
        pq.Push(333, 3);
        pq.Push(5, 1);
        pq.Push(11, 2);
        pq.Push(12, 2);
        pq.Push(12345, 5);
        pq.Push(0, 0);
        pq.Push(123456789, 9);

        Console.WriteLine("\n Aktueller Inhalt der PriorityQueue \n");
        foreach (PriorityQueue.Item i in pq)
            if (i != null)
                Console.WriteLine("{0,10} {1}", i.obj, i.priority);

        Console.WriteLine("\n Die ersten vier Elemente auslesen \n");
        for (int i = 0; i < 4; i++)
        {
            Console.WriteLine("\t {0}-tes Element: {1}", i, pq.Pop());
        }

        Console.WriteLine("\n Aktueller Inhalt der PriorityQueue \n");
        foreach (PriorityQueue.Item i in pq)
            if (i != null)
                Console.WriteLine("{0,10} {1}", i.obj, i.priority);

    }
}
