Skip to content

Instantly share code, notes, and snippets.

@nazarii-piontko
Created January 10, 2020 17:53
Show Gist options
  • Save nazarii-piontko/1c2ad4354c83b220c8cb6f83f5474694 to your computer and use it in GitHub Desktop.
Save nazarii-piontko/1c2ad4354c83b220c8cb6f83f5474694 to your computer and use it in GitHub Desktop.
C# Heap implementation
using System;
using System.Collections;
using System.Collections.Generic;
namespace DataStructures
{
public class Heap<T> : ICollection<T>
{
private const int DefaultCapacity = 16;
private class ComparisonComparer : IComparer<T>
{
private readonly Comparison<T> _comparison;
public ComparisonComparer(Comparison<T> comparison)
{
_comparison = comparison;
}
public int Compare(T x, T y)
{
return _comparison(x, y);
}
}
private readonly List<T> _items;
private readonly IComparer<T> _comparer;
public Heap()
: this(DefaultCapacity, Comparer<T>.Default)
{ }
public Heap(IComparer<T> comparer)
: this(DefaultCapacity, comparer)
{ }
public Heap(Comparison<T> comparison)
: this(DefaultCapacity, new ComparisonComparer(comparison))
{ }
public Heap(int capacity)
: this(capacity, Comparer<T>.Default)
{ }
public Heap(int capacity, Comparison<T> comparison)
: this(capacity, new ComparisonComparer(comparison))
{ }
public Heap(int capacity, IComparer<T> comparer)
{
if (comparer == null)
throw new ArgumentNullException("comparer");
_items = new List<T>(capacity);
_comparer = comparer;
}
public Heap(IEnumerable<T> collection)
: this(collection, Comparer<T>.Default)
{ }
public Heap(IEnumerable<T> collection, Comparison<T> comparison)
: this(collection, new ComparisonComparer(comparison))
{ }
public Heap(IEnumerable<T> collection, IComparer<T> comparer)
{
if (comparer == null)
throw new ArgumentNullException("comparer");
_items = new List<T>(collection);
_comparer = comparer;
BuildMaxHeap();
}
public IEnumerator<T> GetEnumerator()
{
return _items.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public void Add(T item)
{
int i = _items.Count;
_items.Add(item);
while (i > 0 && IsLesser(Parent(i), i))
{
Swap(Parent(i), i);
i = Parent(i);
}
}
public void Clear()
{
_items.Clear();
}
public bool Contains(T item)
{
return _items.Contains(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
_items.CopyTo(array, arrayIndex);
}
bool ICollection<T>.Remove(T item)
{
throw new NotSupportedException("Not supported by this data structure");
}
public int Count
{
get { return _items.Count; }
}
bool ICollection<T>.IsReadOnly
{
get { return false; }
}
public IComparer<T> Comparer
{
get { return _comparer; }
}
public T Maximum
{
get
{
if (_items.Count == 0)
return default(T);
return _items[0];
}
}
public T ExtractMax()
{
if (_items.Count == 0)
return default(T);
T max;
if (_items.Count == 1)
{
max = _items[0];
_items.Clear();
return max;
}
max = _items[0];
_items[0] = _items[_items.Count - 1];
_items.RemoveAt(_items.Count - 1);
MaxHeapify(0);
return max;
}
private void MaxHeapify(int i)
{
int largest = i;
do
{
Swap(largest, i);
i = largest;
int l = Left(i);
int r = Right(i);
largest = l < _items.Count && IsGreater(l, i) ? l : i;
if (r < _items.Count && IsGreater(r, largest))
largest = r;
} while (largest != i);
}
private void BuildMaxHeap()
{
for (int i = _items.Count/2; i >= 0; i--)
MaxHeapify(i);
}
private void Swap(int index1, int index2)
{
if (index1 == index2)
return;
var t = _items[index1];
_items[index1] = _items[index2];
_items[index2] = t;
}
private bool IsGreater(int index1, int index2)
{
return _comparer.Compare(_items[index1], _items[index2]) > 0;
}
private bool IsLesser(int index1, int index2)
{
return _comparer.Compare(_items[index1], _items[index2]) < 0;
}
private static int Parent(int i)
{
return i/2;
}
private static int Left(int i)
{
return 2*i;
}
private static int Right(int i)
{
return 2*i + 1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment