# Priority queue in .Net [closed]

## Problem

I’m seeking for a priority queue or heap data structure implementation in.NET.

There isn’t one in the framework, unless I’m looking in the incorrect place. Is there a good one out there, or should I make my own?

## Solution #1

IntervalHeap from the C5 Generic Collection Library might be of interest to you. To paraphrase the user handbook

It’s a straightforward API.

``````> var heap = new C5.IntervalHeap<int>();
> heap.FindMin();
5
``````

Install the C5 package from Nuget: https://www.nuget.org/packages/C5 or https://github.com/sestoft/C5/

## Solution #2

Here’s my take on a.NET heap.

``````public abstract class Heap<T> : IEnumerable<T>
{
private const int InitialCapacity = 0;
private const int GrowFactor = 2;
private const int MinGrow = 1;

private int _capacity = InitialCapacity;
private T[] _heap = new T[InitialCapacity];
private int _tail = 0;

public int Count { get { return _tail; } }
public int Capacity { get { return _capacity; } }

protected Comparer<T> Comparer { get; private set; }
protected abstract bool Dominates(T x, T y);

protected Heap() : this(Comparer<T>.Default)
{
}

protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
{
}

protected Heap(IEnumerable<T> collection)
: this(collection, Comparer<T>.Default)
{
}

protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
{
if (collection == null) throw new ArgumentNullException("collection");
if (comparer == null) throw new ArgumentNullException("comparer");

Comparer = comparer;

foreach (var item in collection)
{
if (Count == Capacity)
Grow();

_heap[_tail++] = item;
}

for (int i = Parent(_tail - 1); i >= 0; i--)
BubbleDown(i);
}

{
if (Count == Capacity)
Grow();

_heap[_tail++] = item;
BubbleUp(_tail - 1);
}

private void BubbleUp(int i)
{
if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
return; //correct domination (or root)

Swap(i, Parent(i));
BubbleUp(Parent(i));
}

public T GetMin()
{
if (Count == 0) throw new InvalidOperationException("Heap is empty");
return _heap[0];
}

public T ExtractDominating()
{
if (Count == 0) throw new InvalidOperationException("Heap is empty");
T ret = _heap[0];
_tail--;
Swap(_tail, 0);
BubbleDown(0);
return ret;
}

private void BubbleDown(int i)
{
int dominatingNode = Dominating(i);
if (dominatingNode == i) return;
Swap(i, dominatingNode);
BubbleDown(dominatingNode);
}

private int Dominating(int i)
{
int dominatingNode = i;
dominatingNode = GetDominating(YoungChild(i), dominatingNode);
dominatingNode = GetDominating(OldChild(i), dominatingNode);

return dominatingNode;
}

private int GetDominating(int newNode, int dominatingNode)
{
if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
return newNode;
else
return dominatingNode;
}

private void Swap(int i, int j)
{
T tmp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = tmp;
}

private static int Parent(int i)
{
return (i + 1)/2 - 1;
}

private static int YoungChild(int i)
{
return (i + 1)*2 - 1;
}

private static int OldChild(int i)
{
return YoungChild(i) + 1;
}

private void Grow()
{
int newCapacity = _capacity*GrowFactor + MinGrow;
var newHeap = new T[newCapacity];
Array.Copy(_heap, newHeap, _capacity);
_heap = newHeap;
_capacity = newCapacity;
}

public IEnumerator<T> GetEnumerator()
{
return _heap.Take(Count).GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

public class MaxHeap<T> : Heap<T>
{
public MaxHeap()
: this(Comparer<T>.Default)
{
}

public MaxHeap(Comparer<T> comparer)
: base(comparer)
{
}

public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
: base(collection, comparer)
{
}

public MaxHeap(IEnumerable<T> collection) : base(collection)
{
}

protected override bool Dominates(T x, T y)
{
return Comparer.Compare(x, y) >= 0;
}
}

public class MinHeap<T> : Heap<T>
{
public MinHeap()
: this(Comparer<T>.Default)
{
}

public MinHeap(Comparer<T> comparer)
: base(comparer)
{
}

public MinHeap(IEnumerable<T> collection) : base(collection)
{
}

public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
: base(collection, comparer)
{
}

protected override bool Dominates(T x, T y)
{
return Comparer.Compare(x, y) <= 0;
}
}
``````

Some tests:

``````[TestClass]
public class HeapTests
{
[TestMethod]
public void TestHeapBySorting()
{
var minHeap = new MinHeap<int>(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2});
AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

minHeap = new MinHeap<int> { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

var maxHeap = new MaxHeap<int>(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1});
AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());

maxHeap = new MaxHeap<int> {2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4};
AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());
}

private static void AssertHeapSort(Heap<int> heap, IEnumerable<int> expected)
{
var sorted = new List<int>();
while (heap.Count > 0)

Assert.IsTrue(sorted.SequenceEqual(expected));
}
}
``````

## Solution #3

In PowerCollections, I like to use the OrderedBag and OrderedSet classes as priority queues.

## Solution #4

Here’s one I just made; it’s not as efficient (it just uses a sorted dictionary), but it’s straightforward. There are no generic queues because you can insert objects of various types.

``````using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;

namespace PrioQueue
{
public class PrioQueue
{
int total_size;
SortedDictionary<int, Queue> storage;

public PrioQueue ()
{
this.storage = new SortedDictionary<int, Queue> ();
this.total_size = 0;
}

public bool IsEmpty ()
{
return (total_size == 0);
}

public object Dequeue ()
{
if (IsEmpty ()) {
throw new Exception ("Please check that priorityQueue is not empty before dequeing");
} else
foreach (Queue q in storage.Values) {
// we use a sorted dictionary
if (q.Count > 0) {
total_size--;
return q.Dequeue ();
}
}

Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

return null; // not supposed to reach here.
}

// same as above, except for peek.

public object Peek ()
{
if (IsEmpty ())
throw new Exception ("Please check that priorityQueue is not empty before peeking");
else
foreach (Queue q in storage.Values) {
if (q.Count > 0)
return q.Peek ();
}

Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

return null; // not supposed to reach here.
}

public object Dequeue (int prio)
{
total_size--;
return storage[prio].Dequeue ();
}

public void Enqueue (object item, int prio)
{
if (!storage.ContainsKey (prio)) {
}
storage[prio].Enqueue (item);
total_size++;

}
}
}
``````