Skip to main content
added 789 characters in body
Source Link
t3chb0t
  • 44.3k
  • 9
  • 84
  • 190

The Swap method can be much cooler with the tuple syntax to do the operation in only one line. At the same time make it an extension method and pass the two indexes with the new in keyword to pass the values as a reference (value type and reference type both) which has a great potential to improve performance because no copying is involved.

public static void Swap<T>(this IList<T> source, in int x, in int y)
{
    (source[x], source[y]) = (source[y], source[x]);
}

and use it with

m_values.Swap(in offset, in parent);

###values parameter bug

There is a bug in the constructor.

public BinaryHeap(IList<T> values, Func<T, T, bool> comparer)
{
  ...
  _values = values;
  ...
}

It assigns the values to the prviate _values field but an array also implements this interface. This means that if you try to create it with

var bh = new BinaryHeap<int>(new[] { 1, 2, 5, 8 }, (x, y) => x == y);

it'll crash because an array has a fixed size and Grow will fail at _values.Add(default);

You should let the use pass an IEnumerable<T> and call .ToList() yourself to not only be sure it's modifiable but also to make sure nobody modifies it for you out side of the class. Currently I could .Clear() the values and it would crash again.


Oh, one more thing. Since BinaryHeap<T> is a collection it should also implement the IEnumerable<T> interface.

The Swap method can be much cooler with the tuple syntax to do the operation in only one line. At the same time make it an extension method and pass the two indexes with the new in keyword to pass the values as a reference (value type and reference type both) which has a great potential to improve performance because no copying is involved.

public static void Swap<T>(this IList<T> source, in int x, in int y)
{
    (source[x], source[y]) = (source[y], source[x]);
}

and use it with

m_values.Swap(in offset, in parent);

The Swap method can be much cooler with the tuple syntax to do the operation in only one line. At the same time make it an extension method and pass the two indexes with the new in keyword to pass the values as a reference (value type and reference type both) which has a great potential to improve performance because no copying is involved.

public static void Swap<T>(this IList<T> source, in int x, in int y)
{
    (source[x], source[y]) = (source[y], source[x]);
}

and use it with

m_values.Swap(in offset, in parent);

###values parameter bug

There is a bug in the constructor.

public BinaryHeap(IList<T> values, Func<T, T, bool> comparer)
{
  ...
  _values = values;
  ...
}

It assigns the values to the prviate _values field but an array also implements this interface. This means that if you try to create it with

var bh = new BinaryHeap<int>(new[] { 1, 2, 5, 8 }, (x, y) => x == y);

it'll crash because an array has a fixed size and Grow will fail at _values.Add(default);

You should let the use pass an IEnumerable<T> and call .ToList() yourself to not only be sure it's modifiable but also to make sure nobody modifies it for you out side of the class. Currently I could .Clear() the values and it would crash again.


Oh, one more thing. Since BinaryHeap<T> is a collection it should also implement the IEnumerable<T> interface.

Source Link
t3chb0t
  • 44.3k
  • 9
  • 84
  • 190

The Swap method can be much cooler with the tuple syntax to do the operation in only one line. At the same time make it an extension method and pass the two indexes with the new in keyword to pass the values as a reference (value type and reference type both) which has a great potential to improve performance because no copying is involved.

public static void Swap<T>(this IList<T> source, in int x, in int y)
{
    (source[x], source[y]) = (source[y], source[x]);
}

and use it with

m_values.Swap(in offset, in parent);