Skip to content

Instantly share code, notes, and snippets.

@NotFounds
Created February 22, 2017 11:59
Show Gist options
  • Save NotFounds/894ee593ad106b02fc0b6960545a05ed to your computer and use it in GitHub Desktop.
Save NotFounds/894ee593ad106b02fc0b6960545a05ed to your computer and use it in GitHub Desktop.
// Min Heap
public class MinHeap<T> where T: IComparable
{
private List<T> items = new List<T>();
public MinHeap(int size)
{
items = new List<T>(size);
}
public void Add(T item)
{
items.Add(item);
var idx = items.Count - 1;
var parent = idx >> 1;
while (idx > 0 && items[idx].CompareTo(items[parent]) < 0)
{
T tmp = items[idx];
items[idx] = items[parent];
items[parent] = tmp;
idx = parent;
parent >>= 1;
}
}
public T RemoveMin()
{
if (items.Count == 0) throw new InvalidOperationException();
var ret = items[0];
items[0] = items[items.Count - 1];
items.RemoveAt(items.Count - 1);
var idx = 0;
var child = 0;
while (idx < items.Count)
{
var min = idx;
child = idx << 1;
if (child + 1 < items.Count && items[child + 1].CompareTo(items[min]) < 0)
min = child + 1;
if (child + 2 < items.Count && items[child + 2].CompareTo(items[min]) < 0)
min = child + 2;
if (min == idx) break;
var tmp = items[idx];
items[idx] = items[min];
items[min] = tmp;
idx = min;
}
return ret;
}
public T Peek()
{
if (items.Count == 0) throw new InvalidOperationException();
return items[0];
}
public void Clear()
{
items.Clear();
}
public int Count
{
get
{
return items.Count;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment