A C# Priority Queue is a specialized Queue data structure. The distinguishing trait of a Priority Queue is that elements with the highest/lowest priority are dequeued (returned) first. A regular queue on the other hand returns elements in the order they were inserted.

//====================================================
//| Downloaded From                                  |
//| Visual C# Kicks - http://www.vcskicks.com/       |
//| License - http://www.vcskicks.com/license.html   |
//====================================================

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

namespace VCSKicksCollection
{
    /// <summary>
    /// Priority Queue data structure
    /// </summary>
    public class PriorityQueue<T>
        where T : IComparable
    {
        protected List<T> storedValues;

        public PriorityQueue()
        {
            //Initialize the array that will hold the values
            storedValues = new List<T>();

            //Fill the first cell in the array with an empty value
            storedValues.Add(default(T));
        }

        /// <summary>
        /// Gets the number of values stored within the Priority Queue
        /// </summary>
        public virtual int Count
        {
            get
            {
                return storedValues.Count - 1;
            }
        }

        /// <summary>
        /// Returns the value at the head of the Priority Queue without removing it.
        /// </summary>
        public virtual T Peek()
        {
            if (this.Count == 0)
            {
                return default(T);    //Priority Queue empty
            }
            else
            {
                return storedValues[1];    //head of the queue
            }
        }

        /// <summary>
        /// Adds a value to the Priority Queue
        /// </summary>
        public virtual void Enqueue(T value)
        {
            //Add the value to the internal array
            storedValues.Add(value);

            //Bubble up to preserve the heap property,
            //starting at the inserted value
            this.BubbleUp(storedValues.Count - 1);
        }

        /// <summary>
        /// Returns the minimum value inside the Priority Queue
        /// </summary>
        public virtual T Dequeue()
        {
            if (this.Count == 0)
            {
                return default(T);    //queue is empty
            }
            else
            {
                //The smallest value in the Priority Queue is the first item in the array
                T minValue = this.storedValues[1];

                //If there's more than one item, replace the first item in the array with the last one
                if (this.storedValues.Count > 2)
                {
                    T lastValue = this.storedValues[storedValues.Count - 1];

                    //Move last node to the head
                    this.storedValues.RemoveAt(storedValues.Count - 1);
                    this.storedValues[1] = lastValue;

                    //Bubble down
                    this.BubbleDown(1);
                }
                else
                {
                    //Remove the only value stored in the queue
                    storedValues.RemoveAt(1);
                }

                return minValue;
            }
        }

        /// <summary>
        /// Restores the heap-order property between child and parent values going up towards the head
        /// </summary>
        protected virtual void BubbleUp(int startCell)
        {
            int cell = startCell;

            //Bubble up as long as the parent is greater
            while (this.IsParentBigger(cell))
            {
                //Get values of parent and child
                T parentValue = this.storedValues[cell / 2];
                T childValue = this.storedValues[cell];

                //Swap the values
                this.storedValues[cell / 2] = childValue;
                this.storedValues[cell] = parentValue;

                cell /= 2; //go up parents
            }
        }

        /// <summary>
        /// Restores the heap-order property between child and parent values going down towards the bottom
        /// </summary>
        protected virtual void BubbleDown(int startCell)
        {
            int cell = startCell;

            //Bubble down as long as either child is smaller
            while (this.IsLeftChildSmaller(cell) || this.IsRightChildSmaller(cell))
            {
                int child = this.CompareChild(cell);

                if (child == -1) //Left Child
                {
                    //Swap values
                    T parentValue = storedValues[cell];
                    T leftChildValue = storedValues[2 * cell];

                    storedValues[cell] = leftChildValue;
                    storedValues[2 * cell] = parentValue;

                    cell = 2 * cell; //move down to left child
                }
                else if (child == 1) //Right Child
                {
                    //Swap values
                    T parentValue = storedValues[cell];
                    T rightChildValue = storedValues[2 * cell + 1];

                    storedValues[cell] = rightChildValue;
                    storedValues[2 * cell + 1] = parentValue;

                    cell = 2 * cell + 1; //move down to right child
                }
            }
        }

        /// <summary>
        /// Returns if the value of a parent is greater than its child
        /// </summary>
        protected virtual bool IsParentBigger(int childCell)
        {
            if (childCell == 1)
            {
                return false;    //top of heap, no parent
            }
            else
            {
                return storedValues[childCell / 2].CompareTo(storedValues[childCell]) > 0;
            }
            //return storedNodes[childCell / 2].Key > storedNodes[childCell].Key;
        }

        /// <summary>
        /// Returns whether the left child cell is smaller than the parent cell.
        /// Returns false if a left child does not exist.
        /// </summary>
        protected virtual bool IsLeftChildSmaller(int parentCell)
        {
            if (2 * parentCell >= storedValues.Count)
            {
                return false;    //out of bounds
            }
            else
            {
                return storedValues[2 * parentCell].CompareTo(storedValues[parentCell]) < 0;
            }
            //return storedNodes[2 * parentCell].Key < storedNodes[parentCell].Key;
        }

        /// <summary>
        /// Returns whether the right child cell is smaller than the parent cell.
        /// Returns false if a right child does not exist.
        /// </summary>
        protected virtual bool IsRightChildSmaller(int parentCell)
        {
            if (2 * parentCell + 1 >= storedValues.Count)
            {
                return false;    //out of bounds
            }
            else
            {
                return storedValues[2 * parentCell + 1].CompareTo(storedValues[parentCell]) < 0;
            }
            //return storedNodes[2 * parentCell + 1].Key < storedNodes[parentCell].Key;
        }

        /// <summary>
        /// Compares the children cells of a parent cell. -1 indicates the left child is the smaller of the two,
        /// 1 indicates the right child is the smaller of the two, 0 inidicates that neither child is smaller than the parent.
        /// </summary>
        protected virtual int CompareChild(int parentCell)
        {
            bool leftChildSmaller = this.IsLeftChildSmaller(parentCell);
            bool rightChildSmaller = this.IsRightChildSmaller(parentCell);

            if (leftChildSmaller || rightChildSmaller)
            {
                if (leftChildSmaller && rightChildSmaller)
                {
                    //Figure out which of the two is smaller
                    int leftChild = 2 * parentCell;
                    int rightChild = 2 * parentCell + 1;

                    T leftValue = this.storedValues[leftChild];
                    T rightValue = this.storedValues[rightChild];

                    //Compare the values of the children
                    if (leftValue.CompareTo(rightValue) <= 0)
                    {
                        return -1;    //left child is smaller
                    }
                    else
                    {
                        return 1;    //right child is smaller
                    }
                }
                else if (leftChildSmaller)
                {
                    return -1;    //left child is smaller
                }
                else
                {
                    return 1;    //right child smaller
                }
            }
            else
            {
                return 0;    //both children are bigger or don't exist
            }
        }

    }
}