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