Priority queue

Soyez le premier à donner votre avis sur cette source.

Vue 12 628 fois - Téléchargée 256 fois

Description

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).

Source / Exemple :


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

/*************************************************************************************
 *



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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_Bidou
Messages postés
5507
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
42 -
SharpMao> J'ai mis à jour pour que les éléments de même priorités restent dans un ordre FIFO.
cs_Warny
Messages postés
478
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015
-
Je n'ai pas de classe toute faite, c'est peut-être l'occasion justement.
cs_Bidou
Messages postés
5507
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
42 -
Euh j'ai pas trop le temps de regarder en détail pour le moment. Si tu as une classe générique qui s'occupe de ça, je serais curieux de faire quelques teste pour voir la différence entre les deux...
cs_Warny
Messages postés
478
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015
-
Non, c'est pas la peine, va voir cet excelent article de wikipédia : http://fr.wikipedia.org/wiki/B-Arbre
et notamment le lien de visualisation d'un b-arbre pour te faire une idée. C'est la méthode utilisée pour insérer les élements dans une base de données.
cs_Bidou
Messages postés
5507
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
42 -
Autre chose: comment tu fais pour ajouter une Queue dans ta liste de queues?
Tu es obligé de vérifier si elle est existante ou pas, non? Donc tu dois itérer à travers toutes tes queues pour voir si elle existe? même chose quand tu en supprimes une?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.