Max and Min heap implementation with C#
Hi everyone! Today I want to talk about implementation of Max and Min heap with C#.
The reason why you can need them
Three or four months ago I understood that resolving tasks at hackerrank can make you better programmer and gives basic understanding of efficient algorithms.
There are a lot of tasks there should be implemented with heap. But we don’t have heap in .net core library.
Implementation
There are two common ways for implementing heaps. The first one is using list of nodes, where every node contains two child nodes. Using array is the second one (I preferred this one).
Gayle Laakmann McDowell gives a good explanation about implementation of the data structure.
Min heap
public class MinHeap
{
private readonly int[] _elements;
private int _size;
public MinHeap(int size)
{
_elements = new int[size];
}
private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;
private bool HasLeftChild(int elementIndex) => GetLeftChildIndex(elementIndex) < _size;
private bool HasRightChild(int elementIndex) => GetRightChildIndex(elementIndex) < _size;
private bool IsRoot(int elementIndex) => elementIndex == 0;
private int GetLeftChild(int elementIndex) => _elements[GetLeftChildIndex(elementIndex)];
private int GetRightChild(int elementIndex) => _elements[GetRightChildIndex(elementIndex)];
private int GetParent(int elementIndex) => _elements[GetParentIndex(elementIndex)];
private void Swap(int firstIndex, int secondIndex)
{
var temp = _elements[firstIndex];
_elements[firstIndex] = _elements[secondIndex];
_elements[secondIndex] = temp;
}
public bool IsEmpty()
{
return _size == 0;
}
public int Peek()
{
if (_size == 0)
throw new IndexOutOfRangeException();
return _elements[0];
}
public int Pop()
{
if (_size == 0)
throw new IndexOutOfRangeException();
var result = _elements[0];
_elements[0] = _elements[_size - 1];
_size--;
ReCalculateDown();
return result;
}
public void Add(int element)
{
if (_size == _elements.Length)
throw new IndexOutOfRangeException();
_elements[_size] = element;
_size++;
ReCalculateUp();
}
private void ReCalculateDown()
{
int index = 0;
while (HasLeftChild(index))
{
var smallerIndex = GetLeftChildIndex(index);
if (HasRightChild(index) && GetRightChild(index) < GetLeftChild(index))
{
smallerIndex = GetRightChildIndex(index);
}
if (_elements[smallerIndex] >= _elements[index])
{
break;
}
Swap(smallerIndex, index);
index = smallerIndex;
}
}
private void ReCalculateUp()
{
var index = _size - 1;
while (!IsRoot(index) && _elements[index] < GetParent(index))
{
var parentIndex = GetParentIndex(index);
Swap(parentIndex, index);
index = parentIndex;
}
}
}
We are using array as a storage for members of the heap. And doing a few calculation after every add/remove from the top. (The implementation is the same as in the video).
Max heap
If you want to create Max heap, you need to change those methods:
private void ReCalculateDown()
{
int index = 0;
while (HasLeftChild(index))
{
var biggerIndex = GetLeftChildIndex(index);
if (HasRightChild(index) && GetRightChild(index) > GetLeftChild(index))
{
biggerIndex = GetRightChildIndex(index);
}
if (_elements[biggerIndex] < _elements[index])
{
break;
}
Swap(biggerIndex, index);
index = biggerIndex;
}
}
private void ReCalculateUp()
{
var index = _size - 1;
while (!IsRoot(index) && _elements[index] > GetParent(index))
{
var parentIndex = GetParentIndex(index);
Swap(parentIndex, index);
index = parentIndex;
}
}
P.S.
Solving tasks on hackerrank is fun. And I recommend you to try it.
Conclusion
That’s all, thank you for you attention!
Leave a Comment