Skip to content

Instantly share code, notes, and snippets.

@amantix
Created June 9, 2016 16:17
Show Gist options
  • Save amantix/11a2f96054bf7e0dcca099bedba21097 to your computer and use it in GitHub Desktop.
Save amantix/11a2f96054bf7e0dcca099bedba21097 to your computer and use it in GitHub Desktop.
C# binary heap implementation
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;
public class Heap<T>
{
private T[] _array;
private uint _size;
private IComparer<T> _comparer;
public uint Size => _size;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private bool SwapIfGreater(uint key1, uint key2)
{
if (_comparer.Compare(_array[key1], _array[key2]) > 0)
{
T tmp = _array[key1];
_array[key1] = _array[key2];
_array[key2] = tmp;
return true;
}
return false;
}
private void SiftUp()
{
uint cur = _size - 1;
uint parent = (cur - 1)/2;
while(cur>0)
{
if (!SwapIfGreater(cur, parent))
break;
cur = parent;
parent = (cur - 1)/2;
}
}
private void SiftDown()
{
if (_size < 2) return;
uint cur = 0;
uint maxChild;
if (_size == 2) maxChild = 1;
else maxChild = (_comparer.Compare(_array[1], _array[2]) > 0) ? 1u : 2u;
while(cur<_size)
{
maxChild = cur*2 + 1;
if (maxChild > _size - 1) return;
if (maxChild+1 < _size && _comparer.Compare(_array[maxChild], _array[maxChild + 1]) < 0)
++maxChild;
if (!SwapIfGreater(maxChild,cur))
break;
cur = maxChild;
}
}
public Heap(IComparer<T> comparer)
{
_array = new T[2];
_size = 0;
_comparer = comparer;
}
private void Resize()
{
var tmp = new T[_array.Length*2];
_array.CopyTo(tmp, 0);
_array = tmp;
}
public void Add(T item)
{
if (_size == _array.Length)
Resize();
_array[_size++] = item;
SiftUp();
}
public T First => _array[0];
public void PopFirst()
{
_array[0] = _array[--_size];
SiftDown();
}
}
class Program
{
static int compare(int x, int y)
{
return y - x;
}
static void Main(string[] args)
{
Heap<int> h = new Heap<int>(Comparer<int>.Create(compare));// (Comparer<int>.Default);
Random r = new Random();
for (int i = 0; i < 10; ++i)
h.Add(r.Next(10));
while(h.Size>0)
{
Console.WriteLine(h.First);
h.PopFirst();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment