PRIORITY QUEUE

using System;
using System.Collections.Generic;
using System.Text;

/*************************************************************************************
 *
 *  PriorityQueue
 *  Author : Bidou (http://www.csharpfr.com/auteurdetail.aspx?ID=13319)
 *  Blog   : http://blogs.developpeur.org/bidou/
 *  Date   : May 2007
 * 
 *************************************************************************************/

namespace PriorityQueue
{
    /// ---------------------------------------------------------------------------------
    /// <summary>
    /// PriorityQueue.
    /// 
    /// Note: Insertion are done in O(log n)
    /// Note: Removal are done in O(log n) 
    /// </summary>
    /// <typeparam name="T"> The type to store in the priority queue. This type needs to
    /// implement the IComparable interface. </typeparam>
    /// ---------------------------------------------------------------------------------
    public class PriorityQueue<T> where T : IComparable<T>
    {
        private List<InnerItem> _innerList = new List<InnerItem>();
        private int _innerIndex = -1;

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Enqueue a new item.
        /// </summary>
        /// <param name="item"> The item to enqueue. </param>
        /// ---------------------------------------------------------------------------------
        public void Enqueue(T item)
        {
            this._innerList.Add(new InnerItem(++this._innerIndex, item));
            if (this._innerList.Count > 1) this.UpHeap(); // Reorder the tree if needed
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Dequeue.
        /// </summary>
        /// <returns> Return the first item in the queue. </returns>
        /// ---------------------------------------------------------------------------------
        public T Dequeue()
        {
            T first = this.Peek();
            int count = this._innerList.Count - 1;
            this._innerList[0] = this._innerList[count];
            this._innerList.RemoveAt(count);
            this._innerIndex--;
            this.DownHeap();
            return first;
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Get the first item in the queue.
        /// </summary>
        /// <returns> The first item. </returns>
        /// ---------------------------------------------------------------------------------
        public T Peek()
        {
            return this._innerList.Count > 0 ? this._innerList[0].Item : default(T);
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Reorder the tree (down->up).
        /// </summary>
        /// ---------------------------------------------------------------------------------
        private void UpHeap()
        {
            int current = this._innerList.Count - 1;
            int parent = (current - 1) / 2;
            while (this._innerList[current].Item.CompareTo(this._innerList[parent].Item) < 0)
            {
                this.SwitchElements(current, parent);
                current = parent;
                parent = (current - 1) / 2;
            }
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Reorder the tree (up->down).
        /// </summary>
        /// ---------------------------------------------------------------------------------
        private void DownHeap()
        {
            int best = 0; int current = -1;
            int left = 0; int right = 0;

            while(best != current)
            {
                current = best;
                left = 2 * best + 1;
                right = left + 1;

                if (this._innerList.Count > left)
                {
                    int x = this._innerList[best].Item.CompareTo(this._innerList[left].Item);
                    if (x > 0 || (x == 0 && this._innerList[left].Index < this._innerList[best].Index)) best = left;
                }
                if (this._innerList.Count > right)
                {
                    int x = this._innerList[best].Item.CompareTo(this._innerList[right].Item);
                    if (x > 0 || (x == 0 && this._innerList[right].Index < this._innerList[best].Index)) best = right;
                }
                if(best != current) this.SwitchElements(best, current);
            }
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Switch two elements
        /// </summary>
        /// <param name="item1"> The first element. </param>
        /// <param name="item2"> The second element. </param>
        /// ---------------------------------------------------------------------------------
        private void SwitchElements(int item1, int item2)
        {
            InnerItem item = this._innerList[item1];
            this._innerList[item1] = this._innerList[item2];
            this._innerList[item2] = item;
        }

        /// ---------------------------------------------------------------------------------
        /// <summary>
        /// Hold the element (add an index to keep FIFO order with same keys).
        /// </summary>
        /// ---------------------------------------------------------------------------------
        private class InnerItem
        {
            private T _item = default(T);
            private int _index = 0;

            /// ---------------------------------------------------------------------------------
            /// <summary>
            /// Represents an item (a Node in the tree).
            /// </summary>
            /// <param name="index"> The index of the Node. </param>
            /// <param name="item"> The item. </param>
            /// ---------------------------------------------------------------------------------
            public InnerItem(int index, T item)
            {
                this._index = index;
                this._item = item;
            }

            /// ---------------------------------------------------------------------------------
            /// <summary>
            /// Get or set the item.
            /// </summary>
            /// ---------------------------------------------------------------------------------
            public T Item
            {
                get { return this._item; }
                set { this._item = value; }
            }

            /// ---------------------------------------------------------------------------------
            /// <summary>
            /// Get or set the index of the item.
            /// </summary>
            /// ---------------------------------------------------------------------------------
            public int Index
            {
                get { return this._index; }
                set { this._index = value; }
            }
        }
    }
}

Télécharger le zip

13 mai 2007 11:13:22 :

Les éléments de même priorités restent classés dans un ordre FIFO. Quelques modifications dans la description du code.