# Priority Queue using Heap

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++)

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

}
}

public class PriorityQueue<T>
{
private readonly List<Node<T>> _queue = new List<Node<T>>();
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 };
_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; }
}
}
``````