Overview
I was doing some performance optimization patterns when I stumbled upon PriorityQueue and I implemented for that reason Heap data structure, but I wanted you guys to tell me if I did something wrong. I am trying to achieve max performance and slight abstraction over the structure (what I mean by that is I gave the opportunity to the caller to decide if he creates max or min heap).
Code
IHeap.cs
namespace DataStructures.Heap
{
using System.Collections.Generic;
/// <summary>
/// Represents heap data structure.
/// </summary>
/// <typeparam name="T">Type of the parameters stored in the heap.</typeparam>
public interface IHeap<T> : IEnumerable<T>
{
/// <summary>
/// Builds heap out of array.
/// </summary>
/// <param name="array">Array to build heap from.</param>
void Build(T[] array);
/// <summary>
/// Adds element to the heap.
/// </summary>
/// <param name="element">Element to add.</param>
void Add(T element);
/// <summary>
/// Extracts element from the heap.
/// </summary>
/// <returns> Extracted element.</returns>
T Extract();
}
}
HeapType.cs
namespace DataStructures.Heap
{
/// <summary>
/// Used to describe what type a heap will be.
/// </summary>
public enum HeapType
{
/// <summary>
/// Max heap is a heap with largest element on top of each tree and sub-tree
/// when array is represented as a binary tree.
/// </summary>
Max,
/// <summary>
/// Min heap is heap with smallest element on top of each tree and sub-tree
/// when array is represented as a binary tree.
/// </summary>
Min
}
}
Heap.cs
namespace DataStructures.Heap
{
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
/// <summary>
/// Represents max heap data struture.
/// </summary>
/// <typeparam name="T">Type of the elements in the heap.</typeparam>
public class Heap<T> : IHeap<T>
{
private T[] _heap;
private readonly HeapType _heapType;
/// <summary>
/// Used to validate property of the heap. Either smallest
/// element should be always root of each tree and sub-tree in a context of min heap
/// or largest when dealing with max heap.
/// </summary>
private readonly Func<int, int, T[], bool> _heapPropertyValidator;
/// <summary>
/// Initializes a new instance of the <see cref="Heap{T}"/> class.
/// </summary>
/// <param name="heap"> Array of type <typeparamref name="T"/></param>
/// <param name="heapType"> Determines what kind of heap this instance will be. It can be any tye of <see cref="HeapType"/>.</param>
public Heap(T[] heap, HeapType heapType)
{
_heap = heap;
_heapType = heapType;
Count = heap.Length;
switch (heapType)
{
case HeapType.Max:
_heapPropertyValidator =
(comparingIndex, comparingIndex2, array) =>
comparingIndex < Count && Comparer<T>.Default.Compare(array[comparingIndex], array[comparingIndex2]) > 0;
break;
case HeapType.Min:
_heapPropertyValidator =
(comparingIndex, comparingIndex2, array) =>
comparingIndex < Count && Comparer<T>.Default.Compare(array[comparingIndex], array[comparingIndex2]) < 0;
break;
#if DEBUG
default:
throw new ArgumentOutOfRangeException(nameof(heapType), heapType, null);
#endif
}
Build(_heap);
}
/// <summary>
/// Gets total number of elements in the heap.
/// </summary>
public int Count { get; private set; }
public T this[int index]
{
get
{
#if DEBUG
if (index < 0)
{
throw new ArgumentException(nameof(index));
}
#endif
return _heap[index];
}
set
{
#if DEBUG
if (value == null)
{
throw new ArgumentNullException(nameof(value));
}
#endif
_heap[index] = value;
}
}
/// <inheritdoc />
/// <remarks> Takes O(nlogn) time complexity. </remarks>
public void Add(T element)
{
#if DEBUG
if (element == null)
{
throw new ArgumentNullException(nameof(element));
}
#endif
_heap[Count] = element;
Count++;
Heapify(_heap, Count);
}
/// <remarks>
/// Maintains the heap property with the help of <see cref="_heapPropertyValidator"/> function.
/// Takes O(nlogn) time complexity.
/// </remarks>
private void Heapify(T[] array, int index = 0)
{
#if DEBUG
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
#endif
while (true)
{
var left = Left(index);
var right = Right(index);
var toSwap = index;
if(_heapPropertyValidator.Invoke(left, index, array))
{
toSwap = left;
}
if(_heapPropertyValidator.Invoke(right, toSwap, array))
{
toSwap = right;
}
if (toSwap != index)
{
array.Swap(index, toSwap);
index = toSwap;
continue;
}
break;
}
}
///<inheritdoc />
/// <remarks> Takes O(n) time complexity. </remarks>
public void Build(T[] array)
{
#if DEBUG
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
#endif
for (var i = Count / 2; i >= 0; i--)
{
Heapify(array, i);
}
}
/// <inheritdoc />
/// <remarks>
/// This method extracts top element of the heap.
/// For max heap this is max element for min heap this is min element.
/// Time complexity of this method is O(logn).
/// </remarks>
public T Extract()
{
// first element is always max element.
var result = _heap[0];
// swap last element with first one and reduce the count, as we will
// remove last element afterwards.
_heap[0] = _heap[--Count];
_heap = _heap.RemoveAt(Count);
// heapify the heap as we broke the property.
Heapify(_heap);
return result;
}
/// <summary>
/// Sorts the heap without modifying it.
/// </summary>
/// <remarks>
/// This method will sort the heap in asc(when the heap is of type min) and
/// desc(when the heap is of type max). This has O(nlogn) time complexity.
/// </remarks>
/// <returns> Sorted enumerable in descending order.</returns>
public IEnumerable<T> Sort()
{
// TODO: Check if move semantics are available in C#
var heap = new Heap<T>(_heap, _heapType);
var result = new T[Count];
for (var i = 0; i < result.Length; i++)
{
result[i] = heap.Extract();
}
return result;
}
/// <summary>
/// Gets the parent index of the <paramref name="index"/>.
/// </summary>
/// <param name="index">Index to which parent index will be searched for.</param>
/// <returns> Parent index. </returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int Parent(int index)
=> (index & 1) == 0 ? (index >>= 1) - 1 : (index >>= 1);
/// <summary>
/// Gets the index of left child of given index.
/// </summary>
/// <param name="index">Index to found left child index to.</param>
/// <returns> Index of the left child of the element with given index.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int Left(int index)
=> (index <<= 1) + 1;
/// <summary>
/// Gets the index of right child of given index.
/// </summary>
/// <param name="index">Index to found right child index to.</param>
/// <returns> Index of the right child of the element with given index.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int Right(int index)
=> (index <<= 1) + 2;
#region IEnumerable
public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_heap).GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
#endregion
}
}
Extensions.cs
using System;
namespace DataStructures
{
public static class Extensions
{
/// <summary>
/// Swaps two elements at two given indexes.
/// </summary>
/// <typeparam name="T">Type of the elements in the array.</typeparam>
/// <param name="array"> The array which will swap values from.</param>
/// <param name="firstIndex"> Index that will be swaped with index number two.</param>
/// <param name="secondIndex"> Index that will be swaped with index number one.</param>
/// <throws><see cref="ArgumentException"/></throws>
public static void Swap<T>(this T[] array, int firstIndex, int secondIndex)
{
#if DEBUG
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
if (firstIndex > array.Length || firstIndex < 0 ||
secondIndex > array.Length || secondIndex < 0)
{
throw new ArgumentException("One of the indexes is out of range.");
}
#endif
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
/// <summary>
/// Removes element from array at index.
/// </summary>
/// <typeparam name="T">Type of the elements in the array.</typeparam>
/// <param name="array"> Array to remove item from.</param>
/// <param name="index"> Index which will be removed.</param>
/// <returns>Returns new array without the element at passed index.</returns>
public static T[] RemoveAt<T>(this T[] array, int index)
{
#if DEBUG
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
if (index < 0)
{
throw new ArgumentException(nameof(index));
}
#endif
var dest = new T[array.Length - 1];
if (index > 0)
Array.Copy(array, 0, dest, 0, index);
if (index < array.Length - 1)
Array.Copy(array, index + 1, dest, index, array.Length - index - 1);
return dest;
}
}
}
Should I continue abstract the class by providing a way of passing heapPropertyValidator function or this should be concerns to the user of the heap?