Priority Queue Algorithm

The Priority Queue Algorithm is a data structure that allows efficient access to the highest-priority element among a set of elements. It is an abstract data type that supports two primary operations: inserting an element with an associated priority, and removing the element with the highest priority. The priority queue can be implemented using various data structures such as arrays, linked lists, or heaps. Among these, the binary heap, specifically the min-max heap, is the most commonly used data structure for implementing priority queues due to its efficiency in insertion and removal operations. In a priority queue, elements are ordered based on their priority values. The element with the highest priority is dequeued first, while the element with the lowest priority is dequeued last. This ordering can be achieved through either a min-heap, where the element with the smallest priority value is considered the highest priority, or a max-heap, where the element with the largest priority value is considered the highest priority. Applications of priority queues are found in various domains such as scheduling processes in operating systems, handling network packets by routers, and solving graph-based problems like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm.
using System;
using System.Collections.Generic;

namespace AStar
{
    /// <summary>
    /// Generic Priority Queue.
    /// List based.
    /// </summary>
    /// <typeparam name="T">The type that will be stored.
    /// Has to be IComparable of T.</typeparam>
    public class PriorityQueue<T>
        where T : IComparable<T>
    {
        // The underlying structure.
        private readonly List<T> list;

        private readonly bool isDescending;

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        public PriorityQueue() => list = new List<T>();

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        /// <param name="isDescending">Should Reverse Sort order? Default: false.</param>
        public PriorityQueue(bool isDescending)
            : this() => this.isDescending = isDescending;

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        /// <param name="capacity">Initial Capacity.</param>
        public PriorityQueue(int capacity)
            : this(capacity, false)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        /// <param name="collection">Internal Data.</param>
        public PriorityQueue(IEnumerable<T> collection)
            : this(collection, false)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        /// <param name="capacity">Initial Capacity.</param>
        /// <param name="isDescending">Should Reverse Sort order? Default: false.</param>
        public PriorityQueue(int capacity, bool isDescending)
        {
            list = new List<T>(capacity);
            this.isDescending = isDescending;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="PriorityQueue{T}"/> class.
        /// </summary>
        /// <param name="collection">Internal Data.</param>
        /// <param name="isDescending">Should Reverse Sort order? Default: false.</param>
        public PriorityQueue(IEnumerable<T> collection, bool isDescending)
            : this()
        {
            this.isDescending = isDescending;
            foreach (var item in collection)
            {
                Enqueue(item);
            }
        }

        /// <summary>
        /// Gets Number of enqueued items.
        /// </summary>
        public int Count => list.Count;

        /// <summary>
        /// Enqueues an item into the Queue.
        /// </summary>
        /// <param name="x">The item to Enqueue.</param>
        public void Enqueue(T x)
        {
            list.Add(x);
            var i = Count - 1; // Position of x

            while (i > 0)
            {
                var p = (i - 1) / 2; // Start at half of i
                if ((isDescending ? -1 : 1) * list[p].CompareTo(x) <= 0)
                {
                    break;
                }

                list[i] = list[p]; // Put P to position of i
                i = p; // I = (I-1)/2
            }

            if (Count > 0)
            {
                list[i] = x; // If while loop way executed at least once(X got replaced by some p), add it to the list
            }
        }

        /// <summary>
        /// Dequeues the item at the end of the queue.
        /// </summary>
        /// <returns>The dequeued item.</returns>
        public T Dequeue()
        {
            var target = Peek(); // Get first in list
            var root = list[Count - 1]; // Hold last of the list
            list.RemoveAt(Count - 1); // But remove it from the list

            var i = 0;
            while (i * 2 + 1 < Count)
            {
                var a = i * 2 + 1; // Every second entry starting by 1
                var b = i * 2 + 2; // Every second entries neighbour
                var c = b < Count && (isDescending ? -1 : 1) * list[b].CompareTo(list[a]) < 0 ? b : a; // Wether B(B is in range && B is smaller than A) or A

                if ((isDescending ? -1 : 1) * list[c].CompareTo(root) >= 0)
                {
                    break;
                }

                list[i] = list[c];
                i = c;
            }

            if (Count > 0)
            {
                list[i] = root;
            }

            return target;
        }

        /// <summary>
        /// Returns the next element in the queue without dequeueing.
        /// </summary>
        /// <returns>The next element of the queue.</returns>
        public T Peek()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Queue is empty.");
            }

            return list[0];
        }

        /// <summary>
        /// Clears the Queue.
        /// </summary>
        public void Clear() => list.Clear();

        /// <summary>
        /// Returns the Internal Data.
        /// </summary>
        /// <returns>The internal data structure.</returns>
        public List<T> GetData() => list;
    }
}

LANGUAGE:

DARK MODE: