PRIORITY QUEUE

---

Commentaire sur cette source (18)
Ajouter un commentaire et/ou une note

Priority Queue C#

J'imagine que tout le monde connait la class Queue du framework qui permet de faire des piles FIFO.
J'ai cherché une PriorityQueue dans le framework, mais je n'ai rien trouvé à ce sujet... Voici donc une classe générique TRES simple qui met cette fonctionnalité en place.

Les Enqueues et les Dequeues se font dans une complexité d'ordre O(log n) grâce à un arbre binaire, ce qui est assez rapide.
Une priority queue peut être utile quand certains éléments doivent absolument passer avant les autres. Par exemple, un prof qui veut imprimer un document avant des étudiants (si y'a 100 fichiers d'étudiants dans la liste d'attentes, le prof passera devant tout le monde :D).

Suite à la discussion dans les commentaires de cette source, j'ajoute que cet algorithme n'est peut-être pas le meilleur au niveau des performances (ceci dit on a quand même un O(log n) ce qui est très bien) mais il reste (comparé à d'autres solutions plus rapide) très simple à mettre en place. De plus, la place prise en mémoire est très faible (un tableau de n élément suffit).

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; }
            }
        }
    }
}

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

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.

• PETIT EXEMPLE UTILISANT XAML ET WPF
• MISE EN OEUVRE DE DESIGN PATTERN
• PUZZLE AVEC PIÈCES CARRÉES
• TABLE DE MENDELEIEV
• CONNEXION À UN COMPTE GOOGLE ADSENSE

• APPLICATION DE L'ALGO DE WAGNER ET FISHER
• DIJKSTRA EN PRATIQUE
• PID PROPORTIONNEL INTEGRAL DERIVE
• CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE
• GENERATEUR DE LABYRINTHES ALEATOIRE

• APPLICATION DE L'ALGO DE WAGNER ET FISHER
• DIJKSTRA EN PRATIQUE
• GENERATEUR DE LABYRINTHES ALEATOIRE
• GESTION D'UNE MQ SERIES ( MESSAGE QUEUE SERIES ) D'IBM AVEC C#.NET
• ALGORITHME DE PATHFINDING A STAR (A*)