Write a programme to demonstrated Priority Queue using Heap

Solution:

using System;
using System.Collections.Generic;
using System.Linq;

namespace QueueOperation
{
    class Program
    {
        private static void Main()
        {
            var priorityQueue = new PriorityQueue<int>();

            Console.WriteLine("Enter item 5 to Priority Queue");
            for (var i = 0; i < 5; i++)
                priorityQueue.Enqueue(i, Convert.ToInt32(Console.ReadLine()));

            Console.WriteLine("Priority Queue");
            while (priorityQueue.Count > 0)
            {
                Console.WriteLine(priorityQueue.Dequeue());
            }

            Console.ReadLine();
        }
    }

    public class PriorityQueue<T>
    {
        private readonly List<Node<T>> _queue = new List<Node<T>>();
        private readonly bool _isMinPriorityQueue;
        private int _heapSize = -1;
        
        public int Count => _queue.Count;


        public PriorityQueue(bool isMinPriorityQueue = false)
        {
            _isMinPriorityQueue = isMinPriorityQueue;
        }


        public void Enqueue(int priority, T obj)
        {
            var node = new Node<T>() { Priority = priority, Object = obj };
            _queue.Add(node);
            _heapSize++;

            if (_isMinPriorityQueue)
                BuildHeapMin(_heapSize);
            else
                BuildHeapMax(_heapSize);
        }
        public T Dequeue()
        {
            if (_heapSize <= -1) throw new Exception("Queue is empty");

            var returnVal = _queue[0].Object;
            _queue[0] = _queue[_heapSize];
            _queue.RemoveAt(_heapSize);
            _heapSize--;

            if (_isMinPriorityQueue)
                MinHeapify(0);
            else
                MaxHeapify(0);
            return returnVal;

        }
        public void UpdatePriority(T obj, int priority)
        {
            for (var i = 0; i <= _heapSize; i++)
            {
                var node = _queue[i];
                if (!ReferenceEquals(node.Object, obj)) continue;
                node.Priority = priority;
                if (_isMinPriorityQueue)
                {
                    BuildHeapMin(i);
                    MinHeapify(i);
                }
                else
                {
                    BuildHeapMax(i);
                    MaxHeapify(i);
                }
            }
        }

        public bool IsInQueue(T obj)
        {
            return _queue.Any(node => ReferenceEquals(node.Object, obj));
        }

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

        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;
            }
        }
        private void MaxHeapify(int i)
        {
            var left = ChildL(i);
            var right = ChildR(i);

            var 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) return;

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

            var 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) return;

            Swap(lowest, i);
            MinHeapify(lowest);
        }

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

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