Created
June 9, 2016 16:17
-
-
Save amantix/11a2f96054bf7e0dcca099bedba21097 to your computer and use it in GitHub Desktop.
C# binary heap implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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