Introduction

    Unlike ordinary queues, a priority queue allows to insert an object with priority so the highest priority objects can be drawn first in FIFO (First in first out) manner. Once objects with highest priority are fetched, objects with second highest priority can be fetched.

There may be many ways to implement priority queues but most efficient one is using heaps. Insertion can be done in heaps in log n time and we will do Enqueue and Dequeue operations here in log n time.

We can see above maximum element will always be on top. When we remove first element from heap (which is root i.e. 9 in above figure) we will place the last element to its position and move elements accordingly to maintain maximum heap as shown below:

Implementation

    Create a generic class "PriorityQueue" as below:

public class PriorityQueue<T>
{
    class Node
    {
        public int Priority { get; set; }
        public T Object { get; set; }
    }

    //object array
    List<Node> queue = new List<Node>();
    int heapSize = -1;
    bool _isMinPriorityQueue;
    public int Count { get { return queue.Count; } }

    /// <summary>
    /// If min queue or max queue
    /// </summary>
    /// <param name="isMinPriorityQueue"></param>
    public PriorityQueue(bool isMinPriorityQueue = false)
    {
        _isMinPriorityQueue = isMinPriorityQueue;
    }


    public void Enqueue(int priority, T obj){...}
    public T Dequeue(){...}
    public void UpdatePriority(T obj, int priority){...}
    public bool IsInQueue(T obj){...}

    private void BuildHeapMax(int i){...}
    private void BuildHeapMin(int i){...}
    private void MaxHeapify(int i){...}
    private void MinHeapify(int i){...}

    private void Swap(int i, int j)
    {
        var temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }
    private int ChildL(int i)
    {
        return i * 2 + 1;
    }
    private int ChildR(int i)
    {
        return i * 2 + 2;
    }
}

MaxHeapify and MinHeapify methods we have learned in previous article heap sort. We know these functions are required to maintain max and min heaps. We will call these methods in each deletion.

private void MaxHeapify(int i)
{
    int left = ChildL(i);
    int right = ChildR(i);

    int heighst = i;

    if (left <= heapSize && queue[heighst].Priority < queue[left].Priority)
        heighst = left;
    if (right <= heapSize && queue[heighst].Priority < queue[right].Priority)
        heighst = right;

    if (heighst != i)
    {
        Swap(heighst, i);
        MaxHeapify(heighst);
    }
}
private void MinHeapify(int i)
{
    int left = ChildL(i);
    int right = ChildR(i);

    int lowest = i;

    if (left <= heapSize && queue[lowest].Priority > queue[left].Priority)
        lowest = left;
    if (right <= heapSize && queue[lowest].Priority > queue[right].Priority)
        lowest = right;

    if (lowest != i)
    {
        Swap(lowest, i);
        MinHeapify(lowest);
    }
}

Two methods BuildHeapMax and BuildHeapMin we will call in every insertion to make sure Heap property is maintained.

/// <summary>
/// Maintain max heap
/// </summary>
/// <param name="i"></param>
private void BuildHeapMax(int i)
{
    while (i >= 0 && queue[(i - 1) / 2].Priority < queue[i].Priority)
    {
        Swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}
/// <summary>
/// Maintain min heap
/// </summary>
/// <param name="i"></param>
private void BuildHeapMin(int i)
{
    while (i >= 0 && queue[(i - 1) / 2].Priority > queue[i].Priority)
    {
        Swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

Now let's implement Enqueue method

/// <summary>
/// Enqueue the object with priority
/// </summary>
/// <param name="priority"></param>
/// <param name="obj"></param>
public void Enqueue(int priority, T obj)
{
    Node node = new Node() { Priority = priority, Object = obj };
    queue.Add(node);
    heapSize++;
    //Maintaining heap
    if (_isMinPriorityQueue)
        BuildHeapMin(heapSize);
    else
        BuildHeapMax(heapSize);
}

Enqueue method first inserts object in list then calls BuildHeapMax or BuildHeapMin methods based on whether queue is Min-Queue or Max-Queue.

/// <summary>
/// Dequeue the object
/// </summary>
/// <returns></returns>
public T Dequeue()
{
    if (heapSize > -1)
    {
        var returnVal = queue[0].Object;
        queue[0] = queue[heapSize];
        queue.RemoveAt(heapSize);
        heapSize--;
        //Maintaining lowest or highest at root based on min or max queue
        if (_isMinPriorityQueue)
            MinHeapify(0);
        else
            MaxHeapify(0);
        return returnVal;
    }
    else
        throw new Exception("Queue is empty");
}

Dequeue method returns first object in queue and places last element at first then it calls MinHeapify or MaxHeapify methods to maintain heap.

Let's run above code

static void Main(string[] args)
{
    PriorityQueue<int> queue = new PriorityQueue<int>();
    Random rnd = new Random();
    //enqueue
    for (int i = 0; i < 10; i++)
    {
        int x = rnd.Next(3);
        queue.Enqueue(x, x);
    }
    //dequeue
    while (queue.Count > 0)
    {
        Console.WriteLine(queue.Dequeue());
    }
    Console.ReadLine();
}

Output

2

2

2

2

1

1

1

1

0

0

We can see above output is prioritized. There are two additional methods UpdatePriority and IsInQueue I would like to implement.

/// <summary>
/// Updating the priority of specific object
/// </summary>
/// <param name="obj"></param>
/// <param name="priority"></param>
public void UpdatePriority(T obj, int priority)
{
    int i = 0;
    for (; i <= heapSize; i++)
    {
        Node node = queue[i];
        if (object.ReferenceEquals(node.Object, obj))
        {
            node.Priority = priority;
            if (_isMinPriorityQueue)
            {
                BuildHeapMin(i);
                MinHeapify(i);
            }
            else
            {
                BuildHeapMax(i);
                MaxHeapify(i);
            }
        }
    }
}
/// <summary>
/// Searching an object
/// </summary>
/// <param name="obj"></param>
/// <returns></returns>
public bool IsInQueue(T obj)
{
    foreach (Node node in queue)
        if (object.ReferenceEquals(node.Object, obj))
            return true;
    return false;
}

Above methods can be used to update priority of an object and finding an object in queue.

Conclusion

    This priority queue can run in O(log n) time where ordinary queues run in O(1) time. Priority queues are required in some of graph algorithms like Prim's Minimum Spanning Tree and Dijkstra Shortest Path. There are other uses of priority queues like priority operations in Operating Systems.