Skip to content

Instantly share code, notes, and snippets.

@paralleltree
Created March 23, 2015 08:13
Show Gist options
  • Save paralleltree/31045ab26f69b956052c to your computer and use it in GitHub Desktop.
Save paralleltree/31045ab26f69b956052c to your computer and use it in GitHub Desktop.
Implementation of priority queue in C#.
class PriorityQueue
{
public List<int> list;
public int Count { get { return list.Count; } }
public PriorityQueue()
{
list = new List<int>();
}
public PriorityQueue(int count)
{
list = new List<int>(count);
}
public void Enqueue(int x)
{
list.Add(x);
int i = Count - 1;
while (i > 0)
{
int p = (i - 1) / 2;
if (list[p] <= x) break;
list[i] = list[p];
i = p;
}
if (Count > 0) list[i] = x;
}
public int Dequeue()
{
int min = Peek();
int root = list[Count - 1];
list.RemoveAt(Count - 1);
int i = 0;
while (i * 2 + 1 < Count)
{
int a = i * 2 + 1;
int b = i * 2 + 2;
int c = b < Count && list[b] < list[a] ? b : a;
if (list[c] >= root) break;
list[i] = list[c];
i = c;
}
if (Count > 0) list[i] = root;
return min;
}
public int Peek()
{
if (Count == 0) throw new InvalidOperationException("Queue is empty.");
return list[0];
}
public void Clear()
{
list.Clear();
}
}
class PriorityQueue<T> where T : IComparable
{
private List<T> list;
public int Count { get { return list.Count; } }
public readonly bool IsDescending;
public PriorityQueue()
{
list = new List<T>();
}
public PriorityQueue(bool isdesc)
: this()
{
IsDescending = isdesc;
}
public PriorityQueue(int capacity)
: this(capacity, false)
{ }
public PriorityQueue(IEnumerable<T> collection)
: this(collection, false)
{ }
public PriorityQueue(int capacity, bool isdesc)
{
list = new List<T>(capacity);
IsDescending = isdesc;
}
public PriorityQueue(IEnumerable<T> collection, bool isdesc)
: this()
{
IsDescending = isdesc;
foreach (var item in collection)
Enqueue(item);
}
public void Enqueue(T x)
{
list.Add(x);
int i = Count - 1;
while (i > 0)
{
int p = (i - 1) / 2;
if ((IsDescending ? -1 : 1) * list[p].CompareTo(x) <= 0) break;
list[i] = list[p];
i = p;
}
if (Count > 0) list[i] = x;
}
public T Dequeue()
{
T target = Peek();
T root = list[Count - 1];
list.RemoveAt(Count - 1);
int i = 0;
while (i * 2 + 1 < Count)
{
int a = i * 2 + 1;
int b = i * 2 + 2;
int c = b < Count && (IsDescending ? -1 : 1) * list[b].CompareTo(list[a]) < 0 ? b : 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;
}
public T Peek()
{
if (Count == 0) throw new InvalidOperationException("Queue is empty.");
return list[0];
}
public void Clear()
{
list.Clear();
}
}
@johnnygoblue
Copy link

Can you support the input of custom comparator?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment