Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Simple priority queue in C# - what will be better than List with custom Sorter : IComparer?

I would like to implement a priority queue which would inject my objects - Nodes to the queue with respect to one field - f. I have already written List with custom comparer but this would require from me to:

  • enqueue - sort the List after each insertion
  • dequeue - remove the last(instead of first for performance) like so

    myList.RemoveAt(myList.Count - 1);
    

My List should be always sorted according to some field (here I need it to be sorted by f). I also need the ability to add and dequeue the object with lowest value from the list.

Can someone tell me what would be the best approach to this ?

EDIT

dasblinkenlight has a very good answer but just I have realised that I should be able to store duplicates in this container.

like image 998
Patryk Avatar asked Dec 20 '12 22:12

Patryk


People also ask

What is a priority queue in C?

A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first. However, if elements with the same priority occur, they are served according to their order in the queue.

What is a priority queue example?

An ascending order priority queue gives the highest priority to the lower number in that queue. For example, you have six numbers in the priority queue that are 4, 8, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 4, 8, 12, 20.

What is priority of queue write C program to implement priority queue using array?

Implementation of Priority Queue using Arrays in C Priority Queue implementation using array is the one of the basic method to implement Queue. In Priority Queue data who has highest priority remove from the Queue first and second highest priority element after it and so on.

What is simple queue with example?

Simple Queue A simple queue is the most basic queue. In this queue, the enqueue operation takes place at the rear, while the dequeue operation takes place at the front: Its applications are process scheduling, disk scheduling, memory management, IO buffer, pipes, call center phone systems, and interrupt handling.


2 Answers

If you are in .NET 4 or later, you can use a SortedSet<T> class with a custom IComparer<T>.

The class lets you add new objects with the Add method common to all mutable collections. You can retrieve the max element using the Max property, and then call Remove to erase the max from the collection.

Edit: (in response to an edit of the question) If you need to store duplicates, you can use a SortedDictionary<Key,int>, and make a counted set out of it. Again, you have an option of using a custom IComparer<T>. When you enqueue an element, check if it exists already, and increment its count. When dequeueing, again check the count, decrement it, and remove the key only when the count reaches zero.

like image 101
Sergey Kalinichenko Avatar answered Sep 27 '22 17:09

Sergey Kalinichenko


As mentioned earlier, a SortedDictionary gets you part way there, you just need a way of dealing with duplicate priorities. The way of dealing with duplicates in any Map based structure (Dictionary, SortedDictionary, etc.) is to make the value a collection of what you really want the values to be. In your case, it makes the most sense for the value to be a Queue<T>.

Here is a starting place. You can add additional methods such as Count, implementations of IEnumerable, etc. if needed.

/// <summary>
/// 
/// </summary>
/// <typeparam name="TElement">The type of the actual elements that are stored</typeparam>
/// <typeparam name="TKey">The type of the priority.  It probably makes sense to be an int or long, \
/// but any type that can be the key of a SortedDictionary will do.</typeparam>
public class PriorityQueue<TElement, TKey>
{
    private SortedDictionary<TKey, Queue<TElement>> dictionary = new SortedDictionary<TKey, Queue<TElement>>();
    private Func<TElement, TKey> selector;


    public PriorityQueue(Func<TElement, TKey> selector)
    {
        this.selector = selector;
    }

    public void Enqueue(TElement item)
    {
        TKey key = selector(item);
        Queue<TElement> queue;
        if (!dictionary.TryGetValue(key, out queue))
        {
            queue = new Queue<TElement>();
            dictionary.Add(key, queue);
        }

        queue.Enqueue(item);
    }

    public TElement Dequeue()
    {
        if (dictionary.Count == 0)
            throw new Exception("No items to Dequeue:");
        var key = dictionary.Keys.First();

        var queue = dictionary[key];
        var output = queue.Dequeue();
        if (queue.Count == 0)
            dictionary.Remove(key);

        return output;
    }
}
like image 20
Servy Avatar answered Sep 27 '22 18:09

Servy