Last active
January 3, 2017 20:19
-
-
Save johnnyazzi/6020620 to your computer and use it in GitHub Desktop.
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.Generic; | |
using System.Linq; | |
using System.Text; | |
namespace Algorithms | |
{ | |
public class BinaryHeap<T> | |
{ | |
protected T[] _data; | |
protected int _size = 0; | |
protected Comparison<T> _comparison; | |
public BinaryHeap() | |
{ | |
Constructor(4, null); | |
} | |
public BinaryHeap(Comparison<T> comparison) | |
{ | |
Constructor(4, comparison); | |
} | |
public BinaryHeap(int capacity) | |
{ | |
Constructor(capacity, null); | |
} | |
public BinaryHeap(int capacity, Comparison<T> comparison) | |
{ | |
Constructor(capacity, comparison); | |
} | |
private void Constructor(int capacity, Comparison<T> comparison) | |
{ | |
_data = new T[capacity]; | |
_comparison = comparison; | |
if (_comparison == null) | |
_comparison = new Comparison<T>(Comparer<T>.Default.Compare); | |
} | |
public int Size | |
{ | |
get | |
{ | |
return _size; | |
} | |
} | |
/// <summary> | |
/// Add an item to the heap | |
/// </summary> | |
/// <param name="item"></param> | |
public void Insert(T item) | |
{ | |
if (_size == _data.Length) | |
Resize(); | |
_data[_size] = item; | |
HeapifyUp(_size); | |
_size++; | |
} | |
/// <summary> | |
/// Get the item of the root | |
/// </summary> | |
/// <returns></returns> | |
public T Peak() | |
{ | |
return _data[0]; | |
} | |
/// <summary> | |
/// Extract the item of the root | |
/// </summary> | |
/// <returns></returns> | |
public T Pop() | |
{ | |
T item = _data[0]; | |
_size--; | |
_data[0] = _data[_size]; | |
HeapifyDown(0); | |
return item; | |
} | |
private void Resize() | |
{ | |
T[] resizedData = new T[_data.Length * 2]; | |
Array.Copy(_data, 0, resizedData, 0, _data.Length); | |
_data = resizedData; | |
} | |
private void HeapifyUp(int childIdx) | |
{ | |
if (childIdx > 0) | |
{ | |
int parentIdx = (childIdx - 1) / 2; | |
if (_comparison.Invoke(_data[childIdx], _data[parentIdx]) > 0) | |
{ | |
// swap parent and child | |
T t = _data[parentIdx]; | |
_data[parentIdx] = _data[childIdx]; | |
_data[childIdx] = t; | |
HeapifyUp(parentIdx); | |
} | |
} | |
} | |
private void HeapifyDown(int parentIdx) | |
{ | |
int leftChildIdx = 2 * parentIdx + 1; | |
int rightChildIdx = leftChildIdx + 1; | |
int largestChildIdx = parentIdx; | |
if (leftChildIdx < _size && _comparison.Invoke(_data[leftChildIdx], _data[largestChildIdx]) > 0) | |
{ | |
largestChildIdx = leftChildIdx; | |
} | |
if (rightChildIdx < _size && _comparison.Invoke(_data[rightChildIdx], _data[largestChildIdx]) > 0) | |
{ | |
largestChildIdx = rightChildIdx; | |
} | |
if (largestChildIdx != parentIdx) | |
{ | |
T t = _data[parentIdx]; | |
_data[parentIdx] = _data[largestChildIdx]; | |
_data[largestChildIdx] = t; | |
HeapifyDown(largestChildIdx); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment